Problem:


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



Sample input:
5 5
3 5 7 11 13
1
4
9
10
13


Sample output:
31
31
27
23
23

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
A = LIST()

sm = sum([A[i] for i in range(N-1, -1, -2)])
borders = [(INF, sm)]
j = N-3
for i in range(N-2, N//2-1, -1):
    border =  (A[j] + A[i]) // 2
    val = A[i] - A[j]
    sm += val
    borders.append((border, sm))
    j -= 2
borders.sort()

for _ in range(Q):
    x = INT()
    idx = bisect_left(borders, (x, 0))
    print(borders[idx][1])

Submission status: Accepted

Solution code:
from bisect import bisect_left
n, q = map(int, input().split())
a = list(map(int, input().split()))

if n % 2:
    n += 1
    a.insert(0, 0)

border = [(a[2*i+1] + a[i+n//2])//2 for i in range(n//2-1)]

s = sum(a[n//2:])
ans = [s]
for i in range(n//2-1):
    s += -a[i+n//2] + a[2*i+1]
    ans.append(s)

for _ in range(q):
    x = int(input())
    i = bisect_left(border, x)
    print(ans[i])

Submission status: Accepted

Solution code:
import bisect
N,Q = map(int,input().split())
A = list(map(int,input().split()))
X = [int(input()) for i in range(Q)]
A.reverse()

cums = [0]
cums_e = [0]
for i,a in enumerate(A):
    cums.append(cums[-1] + a)
    cums_e.append(cums_e[-1] + (0 if i%2 else a))

borders = []
scores = []
for i in range(1,N//2+N%2):
    b = (A[i] + A[2*i])//2 + 1
    borders.append(b)
    s = cums[i] + cums_e[-1] - cums_e[2*i]
    scores.append(s)
if N%2:
    scores.append(cums[N//2+1])
else:
    scores.append(cums[N//2])

borders.reverse()
scores.reverse()

ans = []
for x in X:
    i = bisect.bisect(borders, x)
    ans.append(scores[i])
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
#参考
#https://atcoder.jp/contests/aising2019/submissions/3995168
 
import bisect
 
N,Q=map(int,input().split())
 
A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0
 
for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]
 
X=[] 
for i in range(Q):
  X.append((int(input()),i))
X.sort(key=lambda x :x[0])
  
 
#yで高橋くんと青木くんの取りたいカードが初めて衝突すると考える。
#このようなyは半分より小さい所にはないので初期値を半分のところとする。
#yがNまで来た時は最初から交互に取る
#Xを小さい順から計算することで、yの値が単調増加になる
y=N//2-1
ans=[0]*Q
for x,i in X:
  #条件式はy<=N-1を最初に持ってこないとA[y]の参照でエラーの可能性
  while y<=N-1 and x>A[y]:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break
  #右端からA[y]までは全て高橋くんが取る
  ans[i]+=Asum[N-1]-Asum[y-1]
  #青木くんはyからN-y個取っているので、その下のところから交互に取る
  if y-(N-y)-1<0:
    continue
  ans[i]+=Asum2[y-(N-y)-1]
 
for i in range(Q):
  print(ans[i])

Submission status: Accepted

Solution code:
#参考
#https://atcoder.jp/contests/aising2019/submissions/3995168

import bisect

N,Q=map(int,input().split())

A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0

for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]

X=[] 
for i in range(Q):
  X.append((int(input()),i))
X.sort(key=lambda x :x[0])
  

#yで高橋くんと青木くんの取りたいカードが初めて衝突すると考える。
#このようなyは半分より小さい所にはないので初期値を半分のところとする。
#yがNまで来た時は最初から交互に取る
#Xを小さい順から計算することで、yの値が単調増加になる
y=N//2-1
ans=[0]*Q
for x,i in X:
  while y<=N-1 and x>A[y]:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break
  #右端からA[y]までは全て高橋くんが取る
  ans[i]+=Asum[N-1]-Asum[y-1]
  #青木くんはyからN-y個取っているので、その下のところから交互に取る
  if y-(N-y)-1<0:
    continue
  ans[i]+=Asum2[y-(N-y)-1]

for i in range(Q):
  print(ans[i])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
a = list(map(int,input().split()))
x = [int(input()) for _ in range (q)]

sort_x = sorted(x)
ans = {}
if n % 2 == 1:
    small_position = 0
    border_position = int((n-1)/2)
else:
    small_position = 1
    border_position = int(n/2)
sum_all = sum(a[border_position:])
a.append(1000000000)
a.append(1000000000)
x_index = 0
flag = False

for compare in a[border_position:]:
    compare_x = sort_x[x_index]
    small_a = a[small_position]
    while 2*sort_x[x_index] - small_a <= compare:
        ans[sort_x[x_index]] = sum_all
        x_index += 1
        if x_index == q:
            flag = True
            break
    sum_all = sum_all + small_a - compare
    small_position += 2
    if flag:
        break
for x_i in x:
    print(ans[x_i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from bisect import bisect
N, Q = map(int, input().split())
A = [0] * (N % 2) + list(map(int, input().split()))

HF = len(A) // 2
li = []
cumsum = [sum(A[HF:])]

for i in range(HF - 1):
    left = A[2 * i + 1]
    right = A[i + HF]
    li += [(left + right) // 2 + 1]
    cumsum += [cumsum[-1] + left - right]

for _ in range(Q):
    X = int(input())
    print(cumsum[bisect(li, X)])

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys

# 整数Xのときの[高橋くんが上から取る連続枚数]が、k枚以下（k+1以上にはならない）かどうか判定する
def check(X, k):
    # 青木くんがLより先にRを取れれば、条件を満たす
    L, R = As[N-2*k-1], As[N-k-1]
    return abs(L-X) > abs(X-R)

N, Q = map(int, input().split())
As = list(map(int, input().split()))
Xs = [(int(input()), iX) for iX in range(Q)]

if N == 2:
    print('\n'.join(map(str, [As[-1]]*Q)))
    sys.exit()

numT = (N+1) // 2  # 高橋くんが取るカードの枚数
Ascs = As[::2] if N % 2 else As[1::2]
Descs = As[::-1]
accAscs = [0] + list(accumulate(Ascs))
accDescs = [0] + list(accumulate(Descs))

# 高橋くんが上から連続k枚を取る場合のスコア
scores = [0] * (numT+1)
for k in range(1, numT+1):
    scores[k] = accDescs[k] + accAscs[numT - k]

# Xの降順で処理する
anss = [0] * Q
k = 1
for X, iX in sorted(Xs, reverse=True):
    # [k枚以下]になる最小のkを求める
    while not check(X, k):
        k += 1
    anss[iX] = scores[k]

print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
def d_nearest_card_game(N, Q, A, X):
    # 最初は、高橋くんは数字の大きなカードを、青木くんはxに近いものから取っていく。
    # するといつか高橋くんが取りたいカードが青木くんに取られているような状況になるので、
    # そこからは2人で値の大きなものから順に取っていく。
    # そのため、2人で順に取っていく領域の広さ(N/2通り)がわかればいい。
    # N/2通りなのは、順に取っていくフェイズの前に2人がそれぞれ固まった領域の
    # カードを取るフェイズがN/2回あるため。
    # (Nが偶数のとき。奇数のときは両者が両端から取っていって
    # 最後に高橋くんが真ん中のカードを取ることがありうる)

    # これらの場合について、境界となるxの値を先に求めておけば、各クエリに対して
    # どの場合に当たるのかを高速に判定できる。

    # 境界となるxは青木くんがまとめて取ることになる領域の左右端の中央にある。
    # 数列のインデックスを右から0-basedで付けていくと、
    # 高橋くんがまとめて取っている領域は 0, 1, ..., i
    # 青木くんがまとめて取っている領域は i+1, i+2, ..., 2i+1
    # 境界となるxは (A[i+1]+A[2i+2])//2 + 1

    # iの値が分かったときに高橋くんの得点を求めるには、
    # Aの累積和とAの右から偶数番目だけ取る累積和を求めておけばいい。
    import bisect

    a = A[::-1]  # 「右から」はわかりづらいので逆にする
    # 累積和と偶数番目だけ足す累積和
    cumsum, evensum = [0] * (N + 1), [0] * (N + 1)
    for k, a_k in enumerate(a):
        cumsum[k + 1] = cumsum[k] + a_k
        evensum[k + 1] = evensum[k] + (a_k if k % 2 == 0 else 0)

    # 得点が変化するxの境界とそのときの得点
    threshold, threshold_score = [], []
    for k in range((N - 1) // 2):
        threshold.append((a[k + 1] + a[2 * k + 2]) // 2 + 1)
        threshold_score.append((cumsum[k + 1] - cumsum[0]) + (evensum[N] - evensum[2 * k + 2]))

    # Aを逆にしたので、もう一度逆にする
    threshold = threshold[::-1]
    threshold_score = threshold_score[::-1]

    ans = []
    for x in X:
        idx = bisect.bisect_right(threshold, x)
        if idx == 0:
            ans.append(cumsum[(N + 1) // 2] - cumsum[0])
        else:
            ans.append(threshold_score[idx - 1])
    ans = '\n'.join(map(str, ans))
    return ans

N, Q = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
X = [int(input()) for _ in range(Q)]
print(d_nearest_card_game(N, Q, A, X))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,q = li()
a = list(li())
x = [ni() for _ in range(q)]


cum_nor = list(accumulate(a))
cum_odd = list(accumulate(a[::2]))
cum_evn = list(accumulate(a[1::2]))
cum_kog = [cum_odd[i//2] if i%2==0 else cum_evn[i//2] for i in range(n)]

# 高橋君が左からtak個取れるならTrue そうでないならFalse
def check(a:list, tak:int, pivot:int):
    if tak > (len(a)+1)//2:
        return False
    
    if pivot-a[-2*tak+1] > a[-tak]-pivot:
        return False
    else:
        return True
        
    
def binsearch(a:list,xi:int):
    low = 1
    high = len(a)
    while high-low > 1:
        mid = (high+low) // 2
        if check(a,mid,xi):
            low = mid
        else:
            high = mid
            
    return low


for xi in x:
    tak = binsearch(a,xi)
    ans = cum_nor[-1] - cum_nor[-tak-1]
    if 2*tak < n:
        ans += cum_kog[-2*tak-1] 
    
    print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_left
from itertools import accumulate

n,q = li()
a = list(li())
x = [ni() for _ in range(q)]


cum_nor = list(accumulate(a))
cum_odd = list(accumulate(a[::2]))
cum_evn = list(accumulate(a[1::2]))
cum_kog = [cum_odd[i//2] if i%2==0 else cum_evn[i//2] for i in range(n)]

# 高橋君が左からtak個取れるならTrue そうでないならFalse
def check(a:list, tak:int, pivot:int):
    if tak > (len(a)+1)//2:
        return False
    
    if pivot-a[-2*tak+1] > a[-tak]-pivot:
        return False
    else:
        return True
        
    
def binsearch(a:list,xi:int):
    low = 1
    high = len(a)
    while high-low > 1:
        mid = (high+low) // 2
        if check(a,mid,xi):
            low = mid
        else:
            high = mid
            
    return low


for xi in x:
    tak = binsearch(a,xi)
    ans = cum_nor[-1] - cum_nor[-tak-1]
    if 2*tak < n:
        ans += cum_kog[-2*tak-1] 
    
    print(ans)

Submission status: Accepted

Solution code:
import bisect

n,q = map(int, input().split())
aList = list(map(int, input().split()))

sumList=[]
sep2SumList=[]
for i in range(n):
    if i==0:
        sumList.append(aList[i])
    else:
        sumList.append(sumList[-1]+aList[i])
    if n%2==0:
        if i%2==1:
            if i==1:
                sep2SumList.append(aList[i])
            else:
                sep2SumList.append(sep2SumList[-1]+aList[i])
    else:
        if i%2==0:
            if i==0:
                sep2SumList.append(aList[i])
            else:
                sep2SumList.append(sep2SumList[-1]+aList[i])

                
sakaime=[]
anskazu=(n+1)//2
for i in range(anskazu):
    sakaime.append((aList[n-(i+1+1)]+aList[n-((i+1+1)*2-1)])//2)
sakaime.reverse()
sakaime=sakaime[1:]

def kotae(x):
    bisect.bisect_left(sakaime,x)
    num=len(sakaime)+1-bisect.bisect_left(sakaime,x)
    if num==len(sakaime)+1:
        ans=sumList[-1]-sumList[-1-num]
    else:
        ans=sumList[-1]-sumList[-1-num]+sep2SumList[(n-num*2+1)//2-1] #+1することで奇数を吸収
    return ans

for i in range(q):
  x=int(input())
  print(kotae(x))

Submission status: Accepted

Solution code:
import bisect

n,q = map(int, input().split())
aList = list(map(int, input().split()))

sumList=[]
sep2SumList=[]
for i in range(n):
    if i==0:
        sumList.append(aList[i])
    else:
        sumList.append(sumList[-1]+aList[i])
    if n%2==0:
        if i%2==1:
            if i==1:
                sep2SumList.append(aList[i])
            else:
                sep2SumList.append(sep2SumList[-1]+aList[i])
    else:
        if i%2==0:
            if i==0:
                sep2SumList.append(aList[i])
            else:
                sep2SumList.append(sep2SumList[-1]+aList[i])

                
sakaime=[]
anskazu=(n+1)//2
for i in range(anskazu):
    sakaime.append((aList[n-(i+1+1)]+aList[n-((i+1+1)*2-1)])//2)
sakaime.reverse()
sakaime=sakaime[1:]

def kotae(x):
    bisect.bisect_left(sakaime,x)
    num=len(sakaime)+1-bisect.bisect_left(sakaime,x)
    if num==len(sakaime)+1:
        ans=sumList[-1]-sumList[-1-num]
    else:
        ans=sumList[-1]-sumList[-1-num]+sep2SumList[(n-num*2+1)//2-1]
    return ans

for i in range(q):
  x=int(input())
  print(kotae(x))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import bisect

n, q = map(int, input().split())
a = list(map(int, input().split()))
X = []
for i in range(q):
    X.append((int(input()), i))
X.sort(key=lambda x: x[0])

# acumはaの累積和
# acum2はaの奇数毎、偶数毎の累積和
acum = [0] * n
acum2 = [0] * n
a_cum = 0
a_cum2 = 0
for i in range(n):
    a_cum += a[i]
    acum[i] = a_cum
    if i - 2 >= 0:
        acum2[i] = acum2[i - 2] + a[i]
    else:
        acum2[i] = a[i]

# 境界をしゃくとり法によって探して、ansに合計値を格納
ans = [0] * q

# a[y] (0-index)を、青木くんと高橋くんがそれぞれ何回目にとることができるのかを考える (青木くんと高橋くんが取り合う境界を見つける）

y = n//2 - 1
for x, i in X:
    # a[y]がxを超えるようにyを繰り上げる (xより小さい所に境界はこないので。こうすると青木くんが何回目にa[y]をとるか考えやすくなる）
    while y <= n-1 and a[y] < x:
        y += 1
    while y <= n-1:
        upper = n - y  # 高橋くんが何回目にa[y]をとるか（とる回数をupperとする）
        lower = y + 1 - bisect.bisect_left(a, 2*x - a[y])  # 青木くんが何回目にa[y]をとるか（とる回数をlowerとする）
        # (lowerに関しては、x ± (a[y] - x)の範囲に含まれている数が、a[y]を何回目にとるかを表すことになる。)
        
        # a[y]を何番目にとるかが、初めて高橋くんの方が大きい、あるいは同じ回数となるまでyを繰り上げる
        if upper > lower:
            y += 1
        else:
            break

    # 境界が決まれば、境界の右の合計と、青木くんが取っていない部分（左側）を青木くんと高橋くんが交互に取っていった時の高橋くんの合計を考えれば良い。
    ans[i] += acum[n-1] - acum[y-1]
    if 2 * y - n <= 0:
        continue
    ans[i] += acum2[2 * y - n - 1]

for i in range(q):
    print(ans[i])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
a = list(map(int, input().split()))
x = [int(input()) for _ in range(q)]
sort_x = sorted(x)
ans = {}
if n%2== 1:
    small_position = 0
    border_position = int((n-1)/2)
else:
    small_position = 1
    border_position = int(n/2)
sum_all = sum(a[border_position:])
a.append(10000000000)
a.append(10000000000)
x_index = 0
flag = False
for compare in a[border_position:]:
    compare_x = sort_x[x_index]
    small_a = a[small_position]
    while 2*sort_x[x_index] - small_a <= compare:
        ans[sort_x[x_index]] = sum_all
        x_index += 1
        if x_index == q:
            flag = True
            break
    sum_all = sum_all + small_a - compare
    small_position += 2
    if flag:
        break

for x_i in x:
    print(ans[x_i])

Submission status: Accepted

Solution code:
import itertools
import sys
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
def f(y):
    return abs(x-A[y])
N, Q = inpl()
A = inpl()
SA = list(itertools.accumulate(A))
if N%2 :
    B = [v for i, v in enumerate(A) if not i%2]
    B = [0] + list(itertools.accumulate(B))
else:
    B = [v for i, v in enumerate(A) if i%2]
    B = [0] + list(itertools.accumulate(B))
    
for _ in range(Q):
    x = int(input())
    lo = 1
    hi = -(-N//2) + 1
    while hi - lo >1:
        mid = (lo+hi)//2
        if mid == 1:
            continue
        if max(f(N-mid-1), f(N-2*mid+1)) <= f(N-mid):
            lo = mid
        else:
            hi = mid    
    print(SA[N-1] - SA[N-lo-1] + B[-((2*lo-N)//2)])

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
if sys.version_info[0:2] >= (3, 3):
    from collections.abc import Sequence
else:
    from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


N, Q = map(int, input().split())
A = [int(s) for s in input().split()]
X = []
for _ in range(Q):
    X.append(int(input()))

# A.sort()
s = [0] * (N + 1)
for i in range(1, N + 1):
    s[i] = s[i - 1] + A[i - 1]
t = [0, A[0]] + [0] * (N - 1)
for i in range(2, N + 1):
    t[i] = t[i - 2] + A[i - 1]


def index_left(x, i):
    val = 2 * x - A[i]
    return bisect_left(A, val)


def nankaime(x, i):
    """requires x <= A[i]"""
    return i - index_left(x, i) + 1


def npi(x, i):
    return nankaime(x, i) + i


def index_right(x, istart):
    ls = LazySequence(lambda i: npi(x, i + istart), N - istart)
    return istart + bisect_left(ls, N) - 1


def getans(x):
    istart = bisect_left(A, x)
    if istart == N:
        return t[N]
    j = index_right(x, istart)
    turn = N - 1 - j
    i = j - turn + 1
    return s[N] - s[j + 1] + (t[i] if i > 0 else 0)


for i in range(Q):
    print(getans(X[i]))

Submission status: Accepted

Solution code:
from itertools import accumulate
import math
import bisect
n,q = map(int, input().split())
a = list(map(int, input().split()))

a_ac = [0] + list(accumulate(a))
taka_ac = [0] + list(accumulate(reversed(a[::-2]))) 
aoki_ac = [0] + list(accumulate(reversed(a[-2::-2]))) 
x = []
y = [10000000000]
z = [taka_ac[-1]]
for i in range(q):
  x.append(int(input()))
if n > 2:
  for i in range((n-1)//2):
    y.append((a[-i-2]+a[-i-3-i])//2)
    z.append(taka_ac[-i-3]+a_ac[-1]-a_ac[-i-3])
y.reverse()
z.reverse()
if n > 2:
  for i in x:
    print(z[bisect.bisect_left(y,i)])
else:
  for i in x:
    print(a[1])

Submission status: Accepted

Solution code:
import bisect

I = lambda:[int(i) for i in input().split()]
n, q = I()
A = [0] + I() if n % 2 else I()

m = len(A)//2
L = []
S = [sum(A[m:])]

for i in range(m-1):
  l = A[2 * i + 1]
  r = A[i + m]
  L+= [(l + r)//2]
  S+= [S[-1] + l - r]

for _ in range(q):
  print(S[bisect.bisect_left(L,int(input()))])

Submission status: Accepted

Solution code:
def emulate(A, x, cumsum, cumsum_skip):
    left = 0
    right = len(A)-2
    while left < right:
        i = (left + right) // 2
        j = len(A) - (len(A) - (i+1)) // 2 - 1
        if x - A[i] <= A[j] - x:
            right = i
        else:
            left = i + 1
    i = (left + right) // 2
    j = len(A) - (len(A) - (i+1)) // 2 - 1
    retval = 0
    if i >= 1:
        retval += cumsum_skip[i-1]
    retval += cumsum[len(A)-1] - cumsum[j-1]
    return retval


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    cumsum = [0] * N
    cumsum_skip = [0] * N
    cumsum[0] = A[0]
    cumsum_skip[0] = A[0] if N % 2 == 1 else 0
    for i in range(1, N):
        cumsum[i] = cumsum[i-1] + A[i]
        if (N - i) % 2 == 1:
            cumsum_skip[i] = cumsum_skip[i-1] + A[i]
        else:
            cumsum_skip[i] = cumsum_skip[i-1]
    for _ in range(Q):
        x = int(input())
        print(emulate(A, x, cumsum, cumsum_skip))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
A = [int(x) for x in input().split()]
B = [a for a in A]
for i in range(N - 2, -1, -1):
  B[i] += B[i + 1]
C = [a for a in A]
for i in range(2, N):
  C[i] += C[i - 2]
D = [0 for i in range(N)]
for i in range(1, N + 1):
  if N - 1 - 2 * i < 0:
    break
  D[N - i] = (A[N - 1 - i] + A[N - 1 - 2 * i]) // 2 + 1
E = [b for b in B]
for i in range(1, N + 1):
  if N - 2 * i - 1 < 0:
    break
  E[N - i] += C[N - 2 * i - 1]
def binsearch(upper, lower, x):
  if x >= D[upper]:
    return upper
  if upper - lower == 1:
    return lower
  else:
    mid = (upper + lower) // 2
    if D[mid] <= x:
      return binsearch(upper, mid, x)
    else:
      return binsearch(mid, lower, x)
for q in range(Q):
  x = int(input())
  print(E[binsearch(N - 1, 0, x)])

Submission status: Accepted

Solution code:
from bisect import bisect_left
N,Q=map(int,input().split())
A=[int(i) for i in input().split()]
P=[]
m=N//2
for k in range(N-m-1):
  P.append((A[k+m]+A[2*(k+m)-N+1])/2)
S,S_o,S_e=[0],[0],[0]
for i in range(N):
  S.append(S[-1]+A[i])
  if i%2==0:
    S_o.append(S_o[-1]+A[i])
    S_e.append(S_e[-1])
  if i%2==1:
    S_o.append(S_o[-1])
    S_e.append(S_e[-1]+A[i])
for q in range(Q):
  a=int(input())
  l=bisect_left(P,a)
  if N%2:
    ans=S[N]-S[N-m+l-1]+S_o[max(N-2*(m-l+1),0)]
  else:
    ans=S[N]-S[N-m+l]+S_e[max(N-2*(m-l),0)]
  print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline

N,Q=map(int,input().split())
A=list(map(int,input().split()))
X=[int(input()) for i in range(Q)]

XLIST=[]
for i in range(1,N//2+1):
    if i+1<=N and 2*i+1<=N:
        XLIST.append((A[-i-1]+A[-2*i-1])/2)



SUM=[0]
for a in A:
    SUM.append(SUM[-1]+a)

SUMODD=[0]
for i in range(N-1,-1,-2):
    SUMODD.append(SUMODD[-1]+A[i])

ANSLIST=[]
ANSLEN=(N+1)//2

for i in range(ANSLEN):
    ANS=0

    ANS+=SUM[-1]-SUM[-1-ANSLEN+i]

    ANS+=SUMODD[-1]-SUMODD[-1-i]

    ANSLIST.append(ANS)
    
XLIST.reverse()

for x in X:
    print(ANSLIST[bisect.bisect_left(XLIST,x)])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import bisect

n,q = [int(i) for i in input().split()]


a = [int(i) for i in input().split()]
if n%2 == 1:
    n+=1
    a.insert(0, 0)


sikiri = [(a[2*i+1] + a[i+n//2])//2 for i in range(n//2-1)]

s = sum(a[n//2:])
ans = [s]
for i in range(n//2-1):
    s = s - a[i+n//2] + a[2*i+1]
    ans.append(s)



#print(a)
#print(sikiri)
#print(ans)


for _ in range(q):
    x = int(input())
    i = bisect.bisect_left(sikiri,x)
    print(ans[i])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
A = list(map(int, input().split()))
X = [int(input()) for i in range(Q)]
B = [0, sum(A[::-1][::2])]
W = [0, sum(A[::-1][::2])]

for i in range(1, (N+1)//2):
    d = (A[-i-1] - A[-i*2-1])
    B.append(B[-1] + d)
    W.append(W[-1] - d)
#print(B, W)
for q in X:
    l, r = 1, (N+1)//2

    while r-l>0:
        a = (r+l)//2+1
        b = A[-a]
        db = b-q
        w = A[-a*2+1]
        dw = q-w
        if dw <= db:
            l = a
        else:
            r = a-1

    print(B[r])

Submission status: Accepted

Solution code:
from math import ceil
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]
AltTake = [0 for a in range(N)]
GetAll = [0 for a in range(N)]
AltTake[0], AltTake[1] = A[0], A[1]
GetAll[-1] = A[-1]
BlockList = [0 for i in range(ceil(N/2))]
maxBlock = ceil(N/2)

for i in range(2, N):
    AltTake[i] = A[i] + AltTake[i-2]
for i in reversed(range(N-1)):
    GetAll[i] = GetAll[i+1] + A[i]
for i in range(ceil(N/2) - 1):
        BlockList[-i-1] = (A[-i-2] + A[-2*i - 3]) // 2 + 1

def BSearch(x, L):
    left, right = 0, len(L)
    while right - left > 1:
        mid = (right + left)//2
        if L[mid] > x:
            right = mid
        else:
            left = mid
    return left

for _ in range(Q):
    block = maxBlock - BSearch(int(input()), BlockList)
    if block == maxBlock: print(GetAll[-block])
    else: print(GetAll[-block] + AltTake[N - block * 2 -1])

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
A=[int(i) for i in input().split()]
X=[int(input()) for i in range(Q)]
if N%2==0:
    ta=N//2
    ao=N//2
else:
    ta=N//2+1
    ao=N//2
L=[0]*(N+1)
M0=[0]*(ta+1)#0,2,4,6...acucsum
M1=[0]*(ao+1)#1,3,5,...accsum
for i in range(N):
    L[i+1]=L[i]+A[i]
for i in range(ta):
    M0[i+1]=M0[i]+A[i*2]
for i in range(ao):
    M1[i+1]=M1[i]+A[i*2+1]

def shin(z):
    ma=N-1
    mi=0
    while ma-mi>1:
        mid=(ma+mi)//2
        if check(mid,z):
            ma=mid
        else:
            mi=mid
    #print(ma)


    nowta = ma
    get = N - 1 - ma + 1  # takahashigets
    ans = 0
    if get == ta:
        ans = L[N] - L[nowta]
    else:
        ans = L[N] - L[nowta]
        nowao = nowta - get - 1
        if nowao % 2 == 1:
            ans += M1[nowao // 2 + 1]

        else:
            ans += M0[nowao // 2 + 1]
    print(ans)

def check(x,z):
    p=(N-1)-x+1
    #print(p)
    if x-p+1<0:
        return False
    if abs(z-A[x-p+1])<=abs(z-A[x]):
        return True
    else:
        return False
for x in X:
    shin(x)

Submission status: Accepted

Solution code:
# D
N, Q = map(int, input().split())
A_list = list(map(int, input().split()))
q_list = [0]*Q
for i in range(Q):
    q_list[i] = int(input())

# precompute

# res
M = (N+1)//2
S1 = [0]*M
S2 = [0]*M

s1 = 0
s2 = 0
for i in range(M):
    s1 += A_list[N-1-i]
    S1[i] = s1
    s2 += A_list[N-1-2*i]
    S2[i] = s2

# bins
bins = [0]*(M-1)
for i in range(M-1):
    bins[i] = (A_list[N - (i+2)] + A_list[N - (2*i+3)]) / 2

# function for binary search
def bisearch(q):
    
    if q > bins[0]:
        return 0
    elif q <= bins[M-2]:
        return M - 1
    
    l = 0
    r = M - 2
    while l < r - 1:
        m = (l + r) // 2
        if q > bins[m]:
            r = m
        else:
            l = m
    return l+1
    
    
if N > 2:
    # first conflict
    for q in q_list:
        r = bisearch(q)
        print(S1[r]+s2-S2[r])
else:
    for q in q_list:
        print(A_list[1])

Submission status: Accepted

Solution code:
import sys

n, q = list(map(int, input().split()))
aaa = list(map(int, input().split()))
xxx = sorted(((int(line), i) for i, line in enumerate(sys.stdin.readlines())), reverse=True)
total = sum(aaa)
tmp = sum(aaa[n // 2:])
ans = [sum(aaa[-1::-2])] * q
if n % 2 == 0:
    l, r = 1, n // 2
else:
    l, r = 0, n // 2
while l < r:
    al, ar = aaa[l], aaa[r]
    m = (al + ar) // 2
    while xxx and xxx[-1][0] <= m:
        x, i = xxx.pop()
        ans[i] = tmp
    if not xxx:
        break
    tmp += al - ar
    l += 2
    r += 1
print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys
import bisect
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    s = [0]*(n+1)
    odd = [0]*(n+1)
    even = [0]*(n+1)
    for i in range(n):
        s[i+1] += s[i]+a[i]
        odd[i+1] += odd[i]
        even[i+1] += even[i]
        if i%2:
            odd[i+1] += a[i]
        else:
            even[i+1] += a[i]
    
    key = []
    value = dict()
    v = 0
    for i in range(n):
        if i == n-1:
            k = pow(10, 9)
            key.append(k)
            value[k] = v
        k = (a[i+(n-i)//2]+a[i])//2
        v = s[i+(n-i)//2]-s[i]
        if (n-i)%2:
            if i%2:
                v += even[max(0, i)]
            else:
                v += odd[max(0, i)]
        else:
            if i%2:
                v += odd[max(0, i-1)]
            else:
                v += even[max(0, i-1)]
        
        key.append(k)
        value[k] = v
    
    sum_a = s[n]
    
    for i in range(q):
        x = int(input())
        k = key[bisect.bisect_left(key, x)]
        ans = sum_a-value[k]
        print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools
MOD = 10**9+7
h, w = map(int, input().split())
x, y = map(int, input().split())
D, L = map(int, input().split())

U = x*y
fact = [0]*(U+1)
fact[0] = 1
for i in range(1, U+1):
    fact[i] = fact[i-1]*i % MOD


invfact = [0]*(U+1)
invfact[U] = pow(fact[U], MOD-2, MOD)
for i in reversed(range(U)):
    invfact[i] = invfact[i+1]*(i+1) % MOD


def nCr(n, r):
    if r < 0 or n < r:
        return 0
    return fact[n]*invfact[r]*invfact[n-r]

  
tmp = 0
for k in range(5):
    for subset in itertools.combinations((0, 0, 1, 1), k):
        dx = subset.count(0)
        dy = subset.count(1)
        if k % 2 == 0:
            tmp += nCr((x-dx)*(y-dy), L+D)
        else:
            tmp -= nCr((x-dx)*(y-dy), L+D)

print((h-x+1)*(w-y+1)*tmp*nCr(L+D, L) % MOD)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from bisect import bisect_left as bl, bisect_right as br
n,q = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
def sub(x, i):
    # i番目を取れるかどうか
    v = a[i]
    if v<x:
        return False
    target = x - (v-x)
    num = i - bl(a, target-0.1)
    return num+1 >= n - i

anss = [None] * q
for j in range(q):
    x = int(input())
    l = bl(a, x)
    r = n-1
    if sub(x, l):
        r = l
    while l<r-1:
        m = (r+l)//2
        if sub(x, m):
            r = m
        else:
            l = m
    # rまではxより大きくて取れる
#     print("r",  r)
    ans = sum(a[r:])
    ii = r-2 - (n-r-1)
    while ii>=0:
        ans += a[ii]
        ii -= 2
    anss[j] = ans
write("\n".join(map(str, anss)))