D - Nearest Card Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 枚のカードがあり、このうち i 枚目のカードには整数 A_i が書かれています。 どの 2 枚のカードに書かれた整数も相異なります。

高橋くんと青木くんはこれらのカードを用いて以下のようなゲームをすることにしました。

  • 青木くんは整数 x を一つ決める。
  • 高橋くんからはじめて、交互にカードを一枚ずつ取っていく。その際、取るカードは以下のように選ぶ。
    • 高橋くんは残っているカードのうち書かれている整数が最も大きいカードを取る。
    • 青木くんは残っているカードのうち書かれている整数が x に最も近いカードを取る。ただしそのようなカードが複数ある場合は、それらのうち書かれている整数が最も小さいカードを取る。
  • 残っているカードがなくなったときゲームは終了する。

Q 個の x の値の候補 X_1, X_2, ..., X_Q が与えられます。 各 i (1 \leq i \leq Q) に対して、青木くんが x = X_i としたときに高橋くんが取ることになるカードに書かれた整数の和を求めてください。

制約

  • 2 \leq N \leq 100,000
  • 1 \leq Q \leq 100,000
  • 1 \leq A_1 < A_2 < ... < A_N \leq 10^9
  • 1 \leq X_i \leq 10^9 (1 \leq i \leq Q)
  • 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 ... A_N
X_1
X_2
:
X_Q

出力

Q 行出力せよ。このうち i 行目 (1 \leq i \leq Q) には x = X_i のときの答えを出力せよ。

入力例 1

5 5
3 5 7 11 13
1
4
9
10
13

出力例 1

31
31
27
23
23

たとえば、x = X_3(= 9) のとき、ゲームは以下のように進行します。

  • 高橋くんが 13 が書かれたカードを取る。
  • 青木くんが 7 が書かれたカードを取る。
  • 高橋くんが 11 が書かれたカードを取る。
  • 青木くんが 5 が書かれたカードを取る。
  • 高橋くんが 3 が書かれたカードを取る。

よって、3 行目には 13 + 11 + 3 = 27 を出力します。

入力例 2

4 3
10 20 30 40
2
34
34

出力例 2

70
60
60

Score : 500 points

Problem Statement

There are N cards. The i-th card has an integer A_i written on it. For any two cards, the integers on those cards are different.

Using these cards, Takahashi and Aoki will play the following game:

  • Aoki chooses an integer x.
  • Starting from Takahashi, the two players alternately take a card. The card should be chosen in the following manner:
    • Takahashi should take the card with the largest integer among the remaining card.
    • Aoki should take the card with the integer closest to x among the remaining card. If there are multiple such cards, he should take the card with the smallest integer among those cards.
  • The game ends when there is no card remaining.

You are given Q candidates for the value of x: X_1, X_2, ..., X_Q. For each i (1 \leq i \leq Q), find the sum of the integers written on the cards that Takahashi will take if Aoki chooses x = X_i.

Constraints

  • 2 \leq N \leq 100 000
  • 1 \leq Q \leq 100 000
  • 1 \leq A_1 < A_2 < ... < A_N \leq 10^9
  • 1 \leq X_i \leq 10^9 (1 \leq i \leq Q)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 ... A_N
X_1
X_2
:
X_Q

Output

Print Q lines. The i-th line (1 \leq i \leq Q) should contain the answer for x = X_i.

Sample Input 1

5 5
3 5 7 11 13
1
4
9
10
13

Sample Output 1

31
31
27
23
23

For example, when x = X_3(= 9), the game proceeds as follows:

  • Takahashi takes the card with 13.
  • Aoki takes the card with 7.
  • Takahashi takes the card with 11.
  • Aoki takes the card with 5.
  • Takahashi takes the card with 3.

Thus, 13 + 11 + 3 = 27 should be printed on the third line.

Sample Input 2

4 3
10 20 30 40
2
34
34

Sample Output 2

70
60
60