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:
import sys
input = sys.stdin.readline
from bisect import *

def judge(x):
    a = N-x
    b = x-bisect_left(A, X-(A[x]-X))+1
    
    return a<=b

def binary_search():
    l, r = bisect_left(A, X), N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

N, Q = map(int, input().split())
A = list(map(int, input().split()))
acc = [0]*(N+1)
eacc = [0]*(N+1)
oacc = [0]*(N+1)

for i in range(N):
    acc[i+1] = acc[i]+A[i]
    
    if i%2==0:
        eacc[i+1] = eacc[i]+A[i]
        oacc[i+1] = oacc[i]
    else:
        eacc[i+1] = eacc[i]
        oacc[i+1] = oacc[i]+A[i]

for _ in range(Q):
    X = int(input())
    border = binary_search()
    ans = acc[N]-acc[border]
    
    if N-2*(N-border)>=0:
        if (N-2*(N-border))%2==0:
            ans += oacc[N-2*(N-border)]
        else:
            ans += eacc[N-2*(N-border)]
    
    print(ans)

Submission status: Accepted

Solution code:
import bisect

n, q = map(int,input().split())
a = list(map(int,input().split()))
a.reverse()
 
cums = [0]*(n+1)
cume = [0]*(n+1)
for i in range(n):
  cums[i+1] = cums[i] + a[i]
  cume[i+1] = cume[i] + a[i]*(1 - i%2)

bo = list()
sc = list()
for i in range(1,(n+1)//2):
    b = (a[i] + a[2*i])//2 + 1
    bo.append(b)
    s = cums[i] + cume[-1] - cume[2*i]
    sc.append(s)
sc.append(cums[(n+1)//2])

bo.reverse()
sc.reverse()
 
for _ in range(q):
    i = bisect.bisect(bo, int(input()))
    print(sc[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
import bisect
n,q = map(int,input().split())
if n%2:
  a = [0]+list(map(int,input().split()))
  n += 1
else:
  a = list(map(int,input().split()))
fs = [a[i] if i%2 else 0 for i in range(n)]
accss = [0]*n
accff = list(accumulate(a))
accfs = list(accumulate(fs))
xls = []
xpt = []
for i in range(n//2):
  xls.append((a[2*i+1]+a[i+n//2])/2)
  if i == 0:
    xpt.append(accff[n-1]-accff[n//2-1])
  else:
    xpt.append(accff[n-1]-accff[i+n//2-1]+accfs[2*i-1])
for _ in range(q):
  x = bisect.bisect_left(xls,int(input()))
  if x >= n//2:
    print(xpt[-1])
  else:
    print(xpt[x])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))
a.reverse()
cs = [0] * (N + 1)
cs2 = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]
for i in range(0, N, 2): cs2[i + 1] = a[i]
for i in range(N): cs2[i + 1] += cs2[i]
#print(cs, cs2)
for _ in range(Q):
  x = int(input())
  ok = 0
  ng = -(-N // 2)
  while ng - ok > 1:
    m = (ok + ng) // 2
    if a[m] + a[m * 2] >= 2 * x: ok = m
    else: ng = m
  res = cs[ok + 1]
  #print(x)
  if (ok + 1) * 2 <= N: res += cs2[-1] - cs2[(ok + 1) * 2]
  print(res)

Submission status: Accepted

Solution code:
def main():
    # アルメリアさんを参考にした いや全然わからん
    from itertools import accumulate
    from bisect import bisect_left
    import sys
    input = sys.stdin.buffer.readline
    N, Q = (int(i) for i in input().split())
    A = [0] + [int(i) for i in input().split()]

    cum = [0] + [a for a in accumulate(A[1:])]
    cum_e = [e for e in accumulate(A[(1 if N & 1 else 0)::2])]

    def binary_search(x):
        ng = 0
        ok = N
        while ok - ng > 1:
            mid = ng + (ok - ng) // 2
            if A[mid] < x:
                ng = mid
            else:
                upper = N - mid + 1
                lower = mid - bisect_left(A, max(1, 2*x-A[mid])) + 1
                if upper > lower:
                    ng = mid
                else:
                    ok = mid
        return ok
    # print(cum, cum_e)
    for query in range(Q):
        x = int(input())
        ok = binary_search(x)
        ans = cum[N] - cum[ok-1]
        t = N - (N-ok+1)*2
        # print(ok, t)
        if t > 0:
            ans += cum_e[t//2]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, q = LI()
    a = LI()
    odd = [0] * n
    even = [0] * n
    def f(mid):
        return abs(a[mid] - x) < abs(a[mid - (n - mid - 1)] - x)
    for i in range(n):
        if i & 1:
            odd[i] += odd[i - 1] + a[i]
        else:
            odd[i] += odd[i - 1]
    acc = list(itertools.accumulate(a))
    for _ in range(q):
        x = II()
        ok = 0
        ng = n
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            if f(mid):
                ok = mid
            else:
                ng = mid
        ok = ng - (n - ng)
        ng -= 1
        ans = acc[-1] - acc[ng]
        if ok < 0:
            pass
        elif n & 1:
            ans += acc[ok]-odd[ok]
        else:
            ans += odd[ok]
        print(ans)
        
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def calc(x):
    l, r = 0, (N+1)//2
    while r - l > 1:
        m = (l+r) // 2
        if A[m] + A[2*m] >= 2 * x:
            l = m
        else:
            r = m
    return l
    
N, Q = map(int, input().split())
A = [int(a) for a in input().split()][::-1]
B = [A[0]] + [0] * (N-1)
for i in range(1, N):
    B[i] = B[i-1] + A[i]
C = [A[0]] + [0] * (N-1)
for i in range(2, N, 2):
    C[i] = C[i-2] + A[i]
C[-1] += C[-2]
for _ in range(Q):
    x = int(input())
    c = calc(x)
    print(B[c] + (C[-1] - C[2*c] if c*2<=N else 0))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

A.reverse()

evenA = [0] * (N + 1)
accA = [0] * (N + 1)

for i in range(1, N + 1):
    evenA[i] = evenA[i - 1] + (A[i - 1] if i % 2 == 1 else 0)
    accA[i] = accA[i - 1] + A[i - 1]

borders = []
scores = []

for i in range(1, N // 2 + N % 2):
    border = (A[i] + A[i * 2]) // 2 + 1
    borders.append(border)

    score = accA[i] + (evenA[N] - evenA[i * 2])
    scores.append(score)

scores.append(accA[N // 2 + N % 2])

borders.reverse()
scores.reverse()

for x in X:
    i = bisect_right(borders, x)
    print(scores[i])

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*q
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=min(nn,n-1)

    for i,ini in ix:
        while check(k)==True:k-=1
        k+=1
        ans[i]=aac[-1]-aac[-k-1]+aac2[-k-1]
    for i in ans:
        print(i)
main()

Submission status: Accepted

Solution code:
from itertools import accumulate,chain
def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

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

if N % 2 == 1:
    A = list(chain((0,),map(int,input().split())))
    N += 1
else:
    A = list(map(int,input().split()))

X = [int(input()) for _ in range(Q)]

oacc = list(chain((0,),accumulate(A[1::2])))
acc = list(chain((0,),accumulate(A)))

check = lambda x: lambda i: x*2 < A[-i]+A[-2*i]
M = N//2
for x in X:
    c = check(x)
    if c(M):
        print(acc[-1]-acc[M])
    elif not c(1):
        print(oacc[-1])
    else:
        i = bisect(M, 1, c)
        if x*2 <= A[-i-1] + A[-2*i-1]:
            i += 1
        s = acc[N]-acc[-i-1]
        if 2*i < N:
            s += oacc[(N-2*i)//2]
        print(s)

Submission status: Accepted

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

a = sorted(a)
ruiseki = [0]*(n+1)
for i in range(n):
    ruiseki[i+1] = ruiseki[i] + a[i]
    
ruiseki2 = [0]*(n+1)
if n % 2 == 1:
    for i in range(n):
        if i % 2 == 0:
            ruiseki2[i+1] = ruiseki2[i] + a[i]
        else:
            ruiseki2[i+1] = ruiseki2[i]

if n % 2 == 0:
    for i in range(n):
        if i % 2 == 1:
            ruiseki2[i+1] = ruiseki2[i] + a[i]
        else:
            ruiseki2[i+1] = ruiseki2[i]

def solve(mid, num):
    r = -((-mid) // 2)
    l = mid
    r_pos = n - r
    l_pos = n - l
    if abs(a[l_pos] - num) <= abs(a[r_pos] - num):
        return True
    else:
        return False

for i in range(q):
    num = query[i]
    ok = 1
    ng = n + 1 
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if solve(mid, num):
            ok = mid
        else:
            ng = mid
    ans = 0
    ans += ruiseki[n] - ruiseki[n-(ok+1)//2]
    nokori = n - ok
    ans += ruiseki2[nokori]
    print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

i = (N & 1) ^ 1
j = N // 2

st = sum(A[j:])

ret_k = []
ret_v = []

while i < j :
    ret_k.append((A[i] + A[j]) // 2)
    ret_v.append(st)
    st = st - A[j] + A[i]
    i += 2
    j += 1
ret_k.append(1e+12)
ret_v.append(st)

for x in X :
    print(ret_v[bisect_left(ret_k, x)])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,Q = II()
A = III()
X = Line(Q,1)

if N==2:
    for _ in range(Q):
        print(A[-1])
    exit()

sum_list = [0]*N
now_odd = 0
now_even = 0
for i in range(N):
    if i%2==0:
        now_even += A[i]
        sum_list[i] = now_even
    else:
        now_odd += A[i]
        sum_list[i] = now_odd        

left_sum = [0]*N
now = 0
for i in range(N)[::-1]:
    now += A[i]
    left_sum[i] = now

for x in X:
    left = 0
    right = N//2
    while (right-left>1):
        mid = left + (right-left)//2
        if abs(A[N-mid-2]-x)<abs(A[N-2*mid-2]-x):
            right = mid
        else:
            left = mid
    right1 = right

    left = 0
    right = N//2 + 1
    while (right-left>1):
        mid = left + (right-left)//2
        if abs(A[N-mid-1]-x)<abs(A[N-2*mid-1]-x):
            right = mid
        else:
            left = mid
    right2 = right

    flag = False
    if right1 != right2:
        flag = True

    ans = left_sum[N-right2]

    if flag:
        if N-right1-right2-2>=0:
            ans += sum_list[N-right1-right2-2]
    else:
        if N-right1-right2-1>=0:
            ans += sum_list[N-right1-right2-1]
    print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,Q = map(int,readline().split())
A = np.array(readline().split(),np.int64)
X = np.array(read().split(),np.int64)

INF=10**15
A = np.concatenate([[-INF,-INF,-INF,-INF],A])

"""
・ある数が後手の右端となるのはどのような場合か
・n番目の右側にr>=1個あるとする
・【長さが奇数のときは、先頭に0を追加しておく】
  → 後手は、[n-r+1,n]をとって、先手は[n+1:]およびn-rを回収する。
・n+1番目をとらない iff r-1個自由にとると n+1番目を含まない iff |A_{n+1}-x| >= |A_{n-r+2}-x|
  iff r = 1 or x <= (A_{n+1}+A_{n-r+2})/2 iff r = 1 or x <= (A_{n+1}+A_{n-r+2})//2
・n-r番目をとらない iff r個自由にとると、n-r番目を含まない iff |A_n-x| < |A_{n-r}-x|
  iff x > (A_n+A_{n-r})/2 iff x > (A_n+A_{n-r})//2
"""

n = np.arange(N+4)
r = N-n+3
ind = (n-r>=0)&(r>=1); n = n[ind]; r = r[ind]

lower = (A[n] + A[n-r])//2 + 1
# upper = (A[n+1] + A[n-r+2])//2 不要

#得点の計算：n+1～の和 + n-rから2つずつ下へ

Acum = np.cumsum(A)
Acum_ev = np.zeros_like(A)
Acum_ev[::2] = A[::2].cumsum()
Acum_ev[1::2] = A[1::2].cumsum()
score = Acum[-1] - Acum[n] + Acum_ev[n-r] + INF + INF

I = np.searchsorted(lower,X,side='right') - 1
answer = score[I]

print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

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

for q in range(Q):
	x = int(input())
	if x >= A[-1]:
		print(even_odd_sum[-1])
	else:
		loc_min = bisect.bisect_left(A, x)
		loc_min = max(loc_min, N // 2)
		loc_max = (loc_min + N) // 2

		t = (loc_min + loc_max) // 2


		#print(x, loc_min, loc_max, t, 2*t - N - 1)
		while (loc_min <= loc_max):

			if 2*t - N - 1 >= 0 and A[t - 1] - x >= x - A[2*t - N - 1]:
				loc_max = t - 1
			elif 2*t - N >= 0 and A[t] - x < x - A[2*t - N]:
				loc_min = t + 1
			elif 2*t - N < 0 and A[t] - x < x - A[0]:
				loc_min = t + 1
			else:
				break

			t = (loc_min + loc_max) // 2
		ans = sum_list[-1] - sum_list[t] + even_odd_sum[2*t - N - 1 + 2]
		print(ans)

Submission status: Accepted

Solution code:
# http://kmjp.hatenablog.jp/entry/2019/01/13/0930
import sys
input = sys.stdin.readline

from bisect import bisect_left

n, q = map(int, input().split())
a = list(map(int, input().split()))
xs = [int(input()) for i in range(q)]

s = [0]*(n+1)
se = [0]*(n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]
    if i :
        se[i+1] = se[i-1]
    se[i+1] += a[i]

def check(x, k):
    if k > n:
        return False

    Tk = (k+1)//2
    i = bisect_left(a, x- (a[n-Tk]-x))
    return i+k <= n

for x in xs:
    left = 0
    right = n+1
    while right-left > 1:
        mid = (left+right)//2
        if check(x, mid):
            left = mid
        else:
            right = mid
    top = (left+1)//2
    ans = 0
    ans += s[n] - s[n-top]
    if left%2:
        left += 1
    ans += se[n-left] if n-left>=0 else 0
    print(ans)

Submission status: Accepted

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

INF = 10**12
n, q = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

# Calc cumrative sum
sum_even = [0] * (n + 1)
sum_odd = [0] * (n + 1)
sum_all = [0] * (n + 1)
for i, item in enumerate(a):
    if i % 2 == 0:
        sum_odd[i+1] = sum_odd[i] + a[i]
        sum_even[i+1] = sum_even[i]
    else:
        sum_even[i+1] = sum_even[i] + a[i]
        sum_odd[i+1] = sum_odd[i]
    sum_all[i+1] = sum_all[i] + a[i]

# Iterate in query
a.append(INF)
ans = []
for i in range(q):
    # Get div of aoki - takahashi
    x = int(input())
    l = 0
    r = n - 1
    # l: aoki takes, r: takahashi takes
    while r - l > 1:
        m = (r + l) // 2
        rng = abs(x - a[m])
        t_num = n - m
        a_num = n - t_num - (bisect.bisect_left(a, x - rng))
        if t_num <= a_num + 1:
            r = m
        else:
            l = m
    rng = abs(x - a[r])
    t_num = n - r
    rest = n - 2 * t_num
    t_sum = sum_all[n] - sum_all[n - t_num]
    a_sum = sum_all[r] - sum_all[r - t_num]

    # Add stripe area
    if n - t_num * 2 > 0:
        if rest % 2 == 0:
            t_sum += sum_even[rest]
            a_sum += sum_odd[rest]
        else:
            t_sum += sum_odd[rest]
            a_sum += sum_even[rest]
    ans.append(t_sum)

print("\n".join([str(item) for item in ans]))

Submission status: Accepted

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

INF = 10**12
n, q = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

# Calc cumrative sum
sum_even = [0] * (n + 1)
sum_odd = [0] * (n + 1)
sum_all = [0] * (n + 1)
for i, item in enumerate(a):
    if i % 2 == 0:
        sum_odd[i+1] = sum_odd[i] + a[i]
        sum_even[i+1] = sum_even[i]
    else:
        sum_even[i+1] = sum_even[i] + a[i]
        sum_odd[i+1] = sum_odd[i]
    sum_all[i+1] = sum_all[i] + a[i]

# Iterate in query
a.append(INF)
ans = []
for i in range(q):
    # Get div of aoki - takahashi
    x = int(input())
    big = bisect.bisect_left(a, x)
    small = big - 1
    if (x - a[small]) ** 2 <= (x - a[big]) ** 2:
        l = small
    else:
        l = big
    r = n - 1
    while r - l > 1:
        m = (r + l) // 2
        rng = abs(x - a[m])
        taka = n - m
        aoki = n - taka - (bisect.bisect_left(a, x - rng))
        if taka <= aoki + 1:
            r = m
        else:
            l = m
    rng = abs(x - a[r])
    taka = n - r
    aoki = n - taka - (bisect.bisect_left(a, x - rng))
    taka_sum = sum_all[n] - sum_all[n - taka]
    aoki_sum = sum_all[r] - sum_all[r - taka]
    rest = n - taka * 2
    if rest > 0:
        if rest % 2 == 0:
            taka_sum += sum_even[rest]
            aoki_sum += sum_odd[rest]
        else:
            taka_sum += sum_odd[rest]
            aoki_sum += sum_even[rest]

    ans.append(taka_sum)
print("\n".join([str(item) for item in ans]))

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect

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

# xに応じて、高橋くんが先頭から何枚連続とれるかを
# 前処理により求めておく
INF = 10**20
B = A[::-1]
Y = [(B[i] + B[2 * i]) // 2 + 1 for i in range(1, (N + 1) // 2)][::-1]
acc1 = list(accumulate(B))
acc2 = list(accumulate(B[2::2][::-1]))[::-1] + [0] * (N - (N - 1) // 2)
ans = '\n'.join(
    str(acc1[i] + acc2[i])
    for i in (
        len(Y) - bisect(Y, x)
        for x in X
    )
)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
n,q = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a,x,y,z = a[::-1],[0],[0],[]
for i in range(n):
    x.append(x[-1]+a[i])
    if 1-i%2: y.append(y[-1]+a[i])
    else: y.append(y[-1])
for i in range((n+1)//2): z.append(-1.0*(a[i]+a[2*i])/2)
for i in range(q):
    p = -int(input())
    m = bisect(z,p)
    if m==len(z): print(x[(n+1)//2])
    else: print(x[m]+y[n]-y[2*m])

Submission status: Accepted

Solution code:
import bisect
N,Q=map(int,input().split())
A=list(map(int,input().split()))
odd=[A[1]]
even=[A[0]]
Sum=[A[0],A[0]+A[1]]
for i in range(2,N):
    Sum.append(Sum[-1]+A[i])
    if i%2==0:
        even.append(even[-1]+A[i])
    elif i%2==1:
        odd.append(odd[-1]+A[i])
change=[]
data=[(0,N//2-1)]
R=N//2-1
L=0
for R in range(N//2,N-1):
    L=2*(R+1)-N
    change.append((A[L-1]+A[R])//2)
    data.append((L,R))
if N%2==1:
    Taka=even
    Aoki=odd
elif N%2==0:
    Taka=odd
    Aoki=even
for q in range(Q):
    x=int(input())
    idx=bisect.bisect_left(change,x)
    Range=data[idx]
    if Range[0]==0:
        print(Sum[-1]-Sum[Range[1]])
    else:
        print(Taka[(Range[0]-1)//2]+Sum[-1]-Sum[Range[1]])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,h,w = IR(3)
    print((n-h+1)*(n-w+1))
    return

#B
def B():
    n = I()
    a,b = LI()
    p = LI()
    k = [0 for i in range(a+1)]
    k += [1 for i in range(b-a)]
    k += [2 for i in range(max(p)+1-b)]
    d = defaultdict(int)
    for i in p:
        d[k[i]] += 1
    ans = min(d[0],d[1],d[2])
    print(ans)
    return

#C
def C():
    h,w = LI()
    s = SR(h)
    bfs_map = [[-1 for i in range(w)] for j in range(h)]
    d = [[0,1],[0,-1],[1,0],[-1,0]]
    ans = 0
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                if bfs_map[y][x] < 0:
                    bfs_map[y][x] = 0
                    a = 1
                    b = 0
                    q = deque()
                    q.append([y,x])
                    while q:
                        n,m = q.popleft()
                        for dy,dx in d:
                            n2 = n+dy
                            m2 = m+dx
                            if 0 <= n2 < h and 0 <= m2 < w:
                                if s[n][m] != s[n2][m2] and bfs_map[n2][m2] < 0:
                                    if s[n2][m2] == "#":a += 1
                                    else:b += 1
                                    bfs_map[n2][m2] = 0
                                    q.append([n2,m2])
                    ans += a*b
    print(ans)
    return

#D
def D():
    n,q = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    c = [a[i] if i%2 else 0 for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
        c[i+1] += c[i]
    for i in range(q):
        x = I()
        l = 0
        r = n
        while r-l > 1:
            m = (l+r)//2
            if abs(a[m]-x) < abs(a[m-(n-m-1)]-x):
                l = m
            else:
                r = m
        l = r-(n-r)
        r -= 1
        ans = b[n-1]-b[r]
        l -= 1
        if l >= 0:
            if not n%2:
                ans += c[l]
            else:
                ans += b[l]-c[l]
        print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
a = list(map(int, input().split()))
s = [0] 
#i~jの和: s[j+1]-s[i]
for p in a:
	s.append(s[-1] + p)
oe = [a[0], a[1]]
#oe[i]: range(i, -1, -2)の和
for i in range(2, n):
	oe.append(oe[-2]+a[i])

for _ in range(q):
	x = int(input())
	if 2*x > a[n-2] + a[n-1]:
		print(oe[n-1])
	elif abs(x - a[0]) <= abs(x - a[n//2]):
		print(s[n] - s[n//2])
	else:
		ok = 0
		ng = n + 1
		while abs(ng-ok) > 1:
			mi = (ng+ok) // 2
			if abs(x - a[n - mi]) <= abs(x - a[n - (mi+1)//2]):
				ok = mi
			else:
				ng = mi
		ans = s[n] - s[n-(ok+1)//2]
		if n - (ok+1)//2 * 2 - 1 >= 0:
			ans += oe[n - (ok+1)//2 * 2 - 1]
		print(ans)

Submission status: Accepted

Solution code:
import bisect
def inpl(): return list(map(int,input().split()))

N, Q = inpl()
A = sorted(inpl(), key=lambda x: -x)
if N % 2:
    N += 1
    A.append(0)

frogsum = [0] * N
cumsum = [0] * N
frogsum[0] = A[0]
frogsum[1] = A[1]
cumsum[0] = A[0]
cumsum[1] = A[0] + A[1]
for i in range(2,N-1):
    frogsum[i] = frogsum[i-2] + A[i]
    cumsum[i] = cumsum[i-1] + A[i]

biavg = [ -(A[i]+A[i*2])/2 for i in range(1,N//2) ]

def nsg(X):
    m = bisect.bisect_left(biavg, -X)
    if m < N//2-1 and biavg[m] == -X:
        m += 1

    return cumsum[m] + frogsum[N-2] - frogsum[m*2]


for _ in range(Q):
    X = int(input())
    print(nsg(X))

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve(A, Q):
    N = len(A)
    A = A[::-1]

    s, es = [0] * (N + 1), [0] * (N + 1)
    for i in range(N):
        s[i + 1] = s[i] + A[i]
        es[i + 1] = es[i] + (A[i] if i % 2 == 0 else 0)

    x_list, sum_t_list = [], []
    for n in range((N - 1) // 2):
        x = (A[n + 1] + A[n * 2 + 2]) // 2 + 1
        sum_t = s[n + 1] + (es[N] - es[n * 2 + 2])
        x_list.append(x)
        sum_t_list.append(sum_t)

    x_list = x_list[::-1]
    sum_t_list = sum_t_list[::-1]

    for _ in range(Q):
        x = int(input())
        p = bisect_right(x_list, x)
        if p == 0:
            print(s[(N + 1) // 2])
        else:
            print(sum_t_list[p - 1])


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    solve(A, Q)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve(A, Q):
    N = len(A)
    A = A[::-1]

    s, es = [0] * (N + 1), [0] * (N + 1)
    for i in range(N):
        s[i + 1] = s[i] + A[i]
        es[i + 1] = es[i] + (A[i] if i % 2 == 0 else 0)

    ths, vals = [], []
    for i in range((N - 1) // 2):
        th = (A[i + 1] + A[i * 2 + 2]) // 2 + 1
        val = (s[i + 1] - s[0]) + (es[N] - es[i * 2 + 2])
        ths.append(th)
        vals.append(val)

    ths = ths[::-1]
    vals = vals[::-1]

    for _ in range(Q):
        x = int(input())
        p = bisect_right(ths, x)
        if p == 0:
            print(s[(N + 1) // 2] - s[0])
        else:
            print(vals[p - 1])


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    solve(A, Q)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 14

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

ALT = [0] * N
if N % 2:
    ALT[0] = A[0]
    for i in range(2, N, 2):
        ALT[i - 1] = ALT[i - 2]
        ALT[i] = ALT[i - 2] + A[i]
else:
    ALT[1] = A[1]
    for i in range(3, N, 2):
        ALT[i - 1] = ALT[i - 2]
        ALT[i] = ALT[i - 2] + A[i]

ALT = [0] + ALT

S = [0] * N + [0]
for i in range(N):
    S[i + 1] = S[i] + A[i]

A = [-INF] + A + [INF]
pos1 = pos2 = 0
x, index = X[0]
for i in range(N + 2):
    if x <= A[i]:
        if A[i] - x < x - A[i - 1]:
            pos1 = pos2 = i
        else:
            pos1 = pos2 = i - 1
        break

ans = [0] * Q
for x, index in X:
    while True:
        cnt1 = pos2 - pos1
        cnt2 = N - pos2 + 1
        if cnt2 - cnt1 >= 2:
            if A[pos2] - x < x - A[pos1 - 1]:
                pos2 += 1
            else:
                pos1 -= 1
        elif cnt1 > cnt2:
            if A[pos2 - 1] - x < x - A[pos1]:
                pos1 += 1
            else:
                pos2 -= 1
        elif A[pos2] - x < x - A[pos1]:
            pos1 += 1
            pos2 += 1
        elif A[pos2 - 1] - x >= x - A[pos1 - 1]:
            pos1 -= 1
            pos2 -= 1
        else:
            break
    ans[index] = S[N] - S[pos2 - 1] + ALT[pos1 - 1]

for a in ans:
    print a