/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の数列 A=(A_1,A_2,\dots,A_N) が与えられます。この A に以下を施すことを「操作」と呼びます。
- まず、 1 \le i \le N を満たす整数 i を選択する。
- 次に、以下の 2 つのうちどちらかを選択し、実行する。
- A_i に 1 を加算する。
- A_i から 1 を減算する。
Q 個の質問に答えてください。
i 個目の質問は以下です。
- 「操作」を 0 回以上何度でも使って A の要素を全て X_i にする時、必要な「操作」の最小回数を求めてください。
制約
- 入力は全て整数
- 1 \le N,Q \le 2 \times 10^5
- 0 \le A_i \le 10^9
- 0 \le X_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \dots A_N X_1 X_2 \vdots X_Q
出力
Q 行にわたって出力せよ。
出力のうち i 行目には、 i 個目の質問に対する答えを整数として出力せよ。
入力例 1
5 3 6 11 2 5 5 5 20 0
出力例 1
10 71 29
A=(6,11,2,5,5) であり、この入力には 3 つの質問が含まれます。
1 つ目の質問について、 A に以下のように 10 回の「操作」を施すことで、 A の要素を全て 5 にすることができます。
- A_1 から 1 減算する。
- A_2 から 1 減算することを 6 度繰り返す。
- A_3 に 1 加算することを 3 度繰り返す。
9 回以下の「操作」で A の要素を全て 5 にすることはできません。
2 つ目の質問について、 A に 71 回の「操作」を施すことで、 A の要素を全て 20 にすることができます。
3 つ目の質問について、 A に 29 回の「操作」を施すことで、 A の要素を全て 0 にすることができます。
入力例 2
10 5 1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353 555555555 321654987 1000000000 789456123 0
出力例 2
3316905982 2811735560 5542639502 4275864946 4457360498
出力が 32bit 整数に収まらない場合もあります。
Score : 400 points
Problem Statement
You are given a sequence of length N: A=(A_1,A_2,\dots,A_N). The following action on this sequence is called an operation.
- First, choose an integer i such that 1 \le i \le N.
- Next, choose and do one of the following.
- Add 1 to A_i.
- Subtract 1 from A_i.
Answer Q questions.
The i-th question is the following.
- Consider performing zero or more operations to change every element of A to X_i. Find the minimum number of operations required to do so.
Constraints
- All values in input are integers.
- 1 \le N,Q \le 2 \times 10^5
- 0 \le A_i \le 10^9
- 0 \le X_i \le 10^9
Input
Input is given from Standard Input in the following format:
N Q A_1 A_2 \dots A_N X_1 X_2 \vdots X_Q
Output
Print Q lines.
The i-th line should contain the answer to the i-th question as an integer.
Sample Input 1
5 3 6 11 2 5 5 5 20 0
Sample Output 1
10 71 29
We have A=(6,11,2,5,5) and three questions in this input.
For the 1-st question, you can change every element of A to 5 in 10 operations as follows.
- Subtract 1 from A_1.
- Subtract 1 from A_2 six times.
- Add 1 to A_3 three times.
It is impossible to change every element of A to 5 in 9 or fewer operations.
For the 2-nd question, you can change every element of A to 20 in 71 operations.
For the 3-rd question, you can change every element of A to 0 in 29 operations.
Sample Input 2
10 5 1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353 555555555 321654987 1000000000 789456123 0
Sample Output 2
3316905982 2811735560 5542639502 4275864946 4457360498
The output may not fit into 32-bit integers.