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

Solution (Python):
def main(n,q,a,x):
  a.reverse()
  keys=[]
  sums1=[0]
  sums2=[0]
  tmp1=0
  tmp2=0
  for i in range(n):
    if i%2==0:tmp1+=a[i]
    tmp2+=a[i]
    sums1.append(tmp1)
    sums2.append(tmp2)
  sums=[]
  for i in range((n-1)//2):
    k=a[i+1]+a[i+1+(i+1)]
    keys.append(k//2+1)
    
    s=sums2[i+1]+sums1[-1]-sums1[i+1+(i+1)]
    sums.append(s)
  sums.append(sums2[(n+2-1)//2])
  keys.append(0)
  sums.reverse()
  keys.reverse()
  from bisect import bisect_right
  
  
  for xx in x:
    idx=bisect_right(keys,xx)-1
    print(sums[idx])



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

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
import bisect

n,q = map(int,readline().split())
a = [0] + list(map(int,readline().split()))
x = [0] + list(map(int,read().split()))

cumsum = [0] * (n+1)
cumsum_eo = [0] * (n+1)

for i in range(1,n+1):
    cumsum[i] = cumsum[i-1] + a[i]
    if(i==1):
        cumsum_eo[1] = a[1]
    else:
        cumsum_eo[i] = cumsum_eo[i-2] + a[i]

ans = []
for xi in x[1:]:
    ok = 0
    ng = (n+4)//2
    cnt=0
    while(ng-ok > 1):
        mid = (ng+ok)//2
        if( mid*2-1 > n):
            ng = mid
            continue

        t_l = a[n+1-mid]
        a_r = a[n-mid]
        a_lr = a[n+1-mid*2+1]

        if(t_l - xi < xi-a_lr ):
            ng = mid
        else:
            ok = mid

        cnt+=1

    t_l_ind = n+1-ok
    a_l_ind = n+1-ok*2

    tmp = cumsum[-1] - cumsum[t_l_ind-1]
    if(a_l_ind>1):
        tmp += cumsum_eo[a_l_ind-1]
    ans.append(tmp)
    

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

Solution (Python):
from bisect import bisect_left

N, Q, *AX = map(int, open(0).read().split())
A, X = AX[:N], AX[N:]

if N % 2 == 1:
    A = [0] + A

M = len(A) // 2
B = []
S = [sum(A[M:])]
for i in range(M - 1):
    l, r = A[2 * i + 1], A[i + M]
    B.append((l + r) // 2)
    S.append(S[-1] + l - r)

for x in X:
    print(S[bisect_left(B, x)])

Solution (Python):
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
            continue
            
        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()

Solution (Python):
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
            continue
            
        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()

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,Q=MI()
    A=LI()
    if N%2==1:
        A+=[0]
        N+=1
    A.sort()
    
    """
    連続する区間or交互
    """
    
    S=[0]*(N+1)
    S2=[0]*(N+1)
    
    for i in range(N):
        S[i+1]=S[i]+A[i]
        
    for i in range(0,N-1):
        S2[i+2]=S2[i]+A[i]
        
    
    
        
    def calc(P):
        
        fi=S[-1]-S[-P-1]
        fi+=S2[-2*P]
        return fi
    
    def ch(X,P):
        
        maxa=A[-P-1]
        mina=A[-2*P+1]
        diff=A[-P]-X
        
        
        if diff<0:
            return False
        if X-diff<=mina and maxa<=X+diff:
            return True
        return False
        
    
    for _ in range(Q):
        x=I()
        
        
        ng=N//2 +1
        ok=1
        while ng-ok>1:
            med=(ok+ng)//2
            if ch(x,med):
                ok=med
            else:
                ng=med
                
        
        print(calc(ok))
            

main()

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union







from bisect import bisect_left, bisect_right 























def main():
    Num = Union[int, float]
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    


    def calc_takahasi_top_n(x):
        
        left = -1    
        right = n - 1    
        while right - left > 1:
            mid = (left + right) // 2
            
            
            takahashi_order = n - mid
            
            aoki_order = bisect_right(L, L[mid]) - bisect_left(L, x - (L[mid] - x))
            if takahashi_order <= aoki_order:
                
                right = mid
            else:
                left = mid
        return n - right

            

    def solve(x):
        top_n = calc_takahasi_top_n(x)
        res = max(0, n - top_n * 2)
        
        
        return rev_acum[top_n] + skip_sum[res]
        
    
    n, q = mi()
    L = lmi()
    query = [ii() for _ in range(q)]
    rev_acum = [0] + list(reversed(L))
    for i in range(n + 1):
        if i > 0:
            rev_acum[i] += rev_acum[i-1]
    skip_sum = [0] + L[:]
    for i in range(n + 1):
        if i > 1:
            skip_sum[i] += skip_sum[i-2]
    
    

    for x in query:
        print(solve(x))


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate,zip_longest
from functools import reduce
import bisect
import sys
input = sys.stdin.readline

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

B = [2*a+1 for a in A] 
A = [2*a for a in A] 
X = [2*x for x in X]

S = list(accumulate(A))
T0 = accumulate(A[::2])
T1 = accumulate(A[1::2])
T = []
for s,t in zip_longest(T0,T1):
    T.append(s)
    T.append(t)
if T[-1] is None:
    T.pop()

maxhigh = 10**16
for x in X:
    if x > (A[-1]+A[-2])//2:
        print(T[-1]//2)
        continue
    NG = maxhigh
    OK = 0
    R = OK
    ans = 0
    while True:
        l = x - R
        r = x + R
        li = bisect.bisect_left(A,l)
        ri = bisect.bisect_right(B,r)
        M = ri-li
        if ri == N-M:
            if li > 0:
                ans += T[li-1]
            break
        if ri == N-M-1:
            li -= 1
            if li > 0:
                ans += T[li-1]
            break
        if ri < N-M:
            OK = R
            R = (R + NG)//2
        if N-M < ri:
            NG = R
            R = (R + OK)//2
    if ri > 0:
        ans += S[N-1] - S[ri-1]
    else:
        ans += S[N-1]
    print(ans//2)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *
from bisect import *

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

N, Q = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
acc = [0]
acco = [0]

for i in range(N):
    acc.append(acc[-1]+A[i])
    
    if i%2==1:
        acco.append(acco[-1]+A[i])
    else:
        acco.append(acco[-1])

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

Solution (Python):
from itertools import accumulate
from bisect import bisect_left

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

csum = list(accumulate(As, initial = 0))
csum_even = list(accumulate(As[::2], initial = 0))
csum_odd = list(accumulate(As[1::2], initial = 0))



def calc_t(X):
    ok = -1
    ng = N+1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        aoki = mid // 2
        taka = mid - aoki
        aoki_max = As[-taka]
        aoki_min_index = bisect_left(As, 2*X - aoki_max)
        if N - taka - aoki_min_index < aoki:
            ng = mid
        else:
            ok = mid
    return ok

for _ in range(Q):
    X = int(input())
    t = calc_t(X)
    s = csum[N] - csum[N - (t+1)//2]
    
    if N % 2 == 0:
        s += csum_odd[(N-t)//2]
    else:
        s += csum_even[(N-t+1)//2]
    print(s)

Solution (Python):
import sys
from bisect import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve(x):
    l=bisect_left(aa,x)
    r=n+1
    while l+1<r:
        j=(l+r)//2
        s=x*2-aa[j-1]
        i=bisect_left(aa,s)
        if j-i>n-j:r=j
        else:l=j
    ans=cs[n]-cs[l]
    if n-(n-l)*2>0:ans+=+cs2[n-(n-l)*2]
    print(ans)

n,q=MI()
aa=LI()
cs=[0]
cs2=[0]*(n+1)
for i,a in enumerate(aa):
    cs.append(cs[-1]+a)
    if i<2:cs2[i+1]=a
    else:cs2[i+1]=cs2[i-1]+a

for _ in range(q):
    x=II()
    solve(x)

Solution (Python):


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo



def slv(N, Q, A, X):

    from itertools import accumulate
    sa = [0] + list(accumulate(A))
    sea = [0] + list(accumulate(a if i % 2 == 0 else 0 for i, a in enumerate(A)))
    soa = [0] + list(accumulate(a if i % 2 == 1 else 0 for i, a in enumerate(A)))

    for x in X:
        def f(n):
            if 2*n-1 > N:
                return 1
            t = abs(x-A[-n])
            a = max(abs(x-A[-n-1]), abs(x-A[-2*n+1]))
            if a <= t:
                return 0
            return 1
        n = Bisect(f).bisect_left(1, 1, N) - 1
        ans = sa[N] - sa[N-n]
        r  = max(0, N - 2*n)
        if r % 2 == 0:
            ans += soa[r] - soa[0]
        else:
            ans += sea[r] - sea[0]
        print(ans)

def main():
    N, Q = read_int_n()
    A = read_int_n()
    X = [read_int() for _ in range(Q)]
    slv(N, Q, A, X)

if __name__ == '__main__':
    main()

Solution (Python):
n,q = map(int,input().split())

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

w = [A[0]]
for i in range(1,n):
    w.append(w[-1]+A[i])

w1 = [0]*n
for i in range(n):
    if (n-1-i)%2 == 0:
        w1[i] = A[i]
    if i > 0:
        w1[i] += w1[i-1]

def solve(x):
    l = 0
    r = n+1
    while r-l > 1:
        m = (r+l)//2
        if A[n-m] <= x:
            r = m
        else:
            if 2*m-1 > n:
                r = m
            else:
                if A[n-m]-x >= x-A[n-2*m+1]:
                    l = m
                else:
                    r = m
    ans = w[-1]-w[n-l-1]
    if n-2*l-1 >= 0:
        ans += w1[n-2*l-1]
    print(ans)

for _ in range(q):
    solve(int(input()))

Solution (Python):
n,q = map(int,input().split())

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

w = [A[0]]
for i in range(1,n):
    w.append(w[-1]+A[i])

w1 = [0]*n
for i in range(n):
    if (n-1-i)%2 == 0:
        w1[i] = A[i]
    if i > 0:
        w1[i] += w1[i-1]

def solve(x):
    l = 0
    r = n+1
    while r-l > 1:
        m = (r+l)//2
        if A[n-m] <= x:
            r = m
        else:
            if 2*m-1 > n:
                r = m
            else:
                if A[n-m]-x >= x-A[n-2*m+1]:
                    l = m
                else:
                    r = m
    ans = w[-1]-w[n-l-1]
    if n-2*l-1 >= 0:
        ans += w1[n-2*l-1]
    print(ans)

for _ in range(q):
    solve(int(input()))

Solution (Python):
import bisect

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

dic = {}

w = [A[0]]
for i in range(1,n):
    w.append(w[-1]+A[i])
w1 = [A[0],0]
w2 = [0,A[1]]
for i in range(2,n):
    if i%2 == 0:
        w1.append(w1[-2]+A[i])
        w2.append(0)
    else:
        w2.append(w2[-2]+A[i])
        w1.append(0)

def solve(x):
    if x in dic:
        print(dic[x])
        return 
    if x >= A[-1]:
        count = max(w1[-1],w2[-1])
        dic[x] = count
        print(count)
        return
    l = 0
    r = 10**10
    while r > l+1:
        m = (r+l)//2
        li = bisect.bisect_left(A,x-m)
        ri = bisect.bisect_right(A,x+m)
        if n-ri == ri-li:
            count = w[-1]-w[ri-1]
            li -= 1
            if li>= 0:
                if li%2 == 0:
                    count += w1[li]
                else:
                    count += w2[li]
            dic[x] = count
            print(count)
            return 0
        if n-ri == ri-li+1:
            count = w[-1]-w[ri-1]
            li -= 2
            if li>= 0:
                if li%2 == 0:
                    count += w1[li]
                else:
                    count += w2[li]
            dic[x] = count
            print(count)
            return 0
        if A[ri-1] == x+m:
            ri2 = ri-1
            if n-ri2 == ri2-li:
                count = w[-1]-w[ri2-1]
                li -= 1
                if li>= 0:
                    if li%2 == 0:
                        count += w1[li]
                    else:
                        count += w2[li]
                dic[x] = count
                print(count)
                return 0
            elif n-ri2 == ri2-li+1:
                count = w[-1]-w[ri2-1]
                li -= 2
                if li>= 0:
                    if li%2 == 0:
                        count += w1[li]
                    else:
                        count += w2[li]
                dic[x] = count
                print(count)
                return 0
        if 2*ri > n+li:
            r = m
        else:
            l = m
    
    count = max(w1[-1],w2[-1])
    dic[x] = count
    print(count)
    return

for _ in range(q):
    x = int(input())
    solve(x)

Solution (Python):
import sys
input = sys.stdin.readline
n, q = map(int,input().split())
A = list(map(int,input().split()))[::-1]
X = [int(input()) for i in range(q)]

S = [A[0]]
for i in range(1, n):
    S.append(S[-1] + A[i])

AA = A[::-1]
T = [AA[0], AA[1]]
for i in range(2, n):
    T.append(T[-2] + AA[i])

su = sum(A)


for i in range(q):
    l = 0
    r = (n+1)//2-1 + 1
    m = (l+r)//2
    x = X[i]
    while r-l > 1:
        
        if m == 0 or abs(x-A[m]) >= abs(x-A[m*2]):
            l = m
        else:
            r = m
        m = (l+r)//2
    ans = S[l]
    
    if n - 2*(l+1) > 0:
        ans += T[n-2*(l+1)-1]
    print(ans)

Solution (Python):
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):
    
    v = a[i]
    target = x - (v-x)
    num = i - bl(a, target)
    return num+1 >= n - i

anss = [None] * q
cumsum1 = [0] * n
cumsum0 = [0] * n
cumsum = [0] * n
for i in range(n):
    if i%2:
        cumsum1[i] = cumsum1[i-1] + a[i]
        cumsum0[i] = cumsum0[i-1]
    else:
        cumsum0[i] = cumsum0[i-1] + a[i]
        cumsum1[i] = cumsum1[i-1]
    cumsum[i] = cumsum[i-1] + a[i]

for j in range(q):
    x = int(input())
    l = 0
    r = n-1
    while l<r-1:
        m = (r+l)//2
        if sub(x, m):
            r = m
        else:
            l = m
    

    ans = cumsum[-1] - cumsum[r-1]
    ii = r-2 - (n-r-1)
    if ii>=0:
        if ii%2:
            ans += cumsum1[ii]
        else:
            ans += cumsum0[ii]
    anss[j] = ans
write("\n".join(map(str, anss)))

Solution (Python):
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):
    
    v = a[i]
    target = x - (v-x)
    num = i - bl(a, target-0.1)
    return num+1 >= n - i

anss = [None] * q
cumsum1 = [0] * n
cumsum0 = [0] * n
cumsum = [0] * n
for i in range(n):
    if i%2:
        cumsum1[i] = cumsum1[i-1] + a[i]
        cumsum0[i] = cumsum0[i-1]
    else:
        cumsum0[i] = cumsum0[i-1] + a[i]
        cumsum1[i] = cumsum1[i-1]
    cumsum[i] = cumsum[i-1] + a[i]

for j in range(q):
    x = int(input())
    l = 0
    r = n-1
    while l<r-1:
        m = (r+l)//2
        if sub(x, m):
            r = m
        else:
            l = m
    

    ans = cumsum[-1] - cumsum[r-1]
    ii = r-2 - (n-r-1)
    if ii>=0:
        if ii%2:
            ans += cumsum1[ii]
        else:
            ans += cumsum0[ii]
    anss[j] = ans
write("\n".join(map(str, anss)))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *
from bisect import *

def judge(x):
    tak = N-x
    aoki = x-bisect_left(A, 2*X-A[x])+1
    
    return tak<=aoki

def binary_search():
    l, r = mark, 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]
acc_e = [0]

for i in range(N):
    acc.append(acc[-1]+A[i])
    acc_e.append(acc_e[-1]+(A[i] if i%2==0 else 0))

for _ in range(Q):
    X = int(input())
    mark = bisect_left(A, X)
    border = binary_search()
    ans = acc[-1]-acc[border]
    c = N-border
    
    if 2*c>=N:
        print(ans)
        continue
    
    if (N-2*c-1)%2==0:
        ans += acc_e[N-2*c]
    else:
        ans += acc[N-2*c]-acc_e[N-2*c]
    
    print(ans)

Solution (Python):
import sys
from bisect import bisect_left

def solve():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = [int(a) for a in input().split()]
    X = [int(input()) for _ in range(Q)]
    cont = [0] * N
    cont[N-1] = A[N-1]
    for i in reversed(range(N-1)): cont[i] = cont[i+1] + A[i]
    change = [0] * N
    change[0] = A[0]
    change[1] = A[1]
    for i in range(2, N): change[i] = change[i-2] + A[i]
    upperBound = [-1] * N
    for i in range((N + 1)// 2): 
        target = A[N-i-1]
        lower = A[(N-i-1) - i]
        upperBound[N-i-1] = (target + lower) // 2
    upperBound[N-1] = 10 ** 10
    Ans = [0] * Q
    for i, x in enumerate(X):
        pos = bisect_left(upperBound, x)
        Ans[i] += cont[pos] 
        if N - (N - pos) * 2 - 1 >= 0: Ans[i] += change[N - (N - pos) * 2 - 1]
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import bisect
import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
A=list(map(int,input().split()))
if N%2==1:
    data1=[A[i] for i in range(0,N)]
    for i in range(1,N):
        data1[-i-1]+=data1[-i]

    data2=[A[2*i] for i in range(0,N//2+1)]
    for i in range(1,len(data2)):
        data2[i]+=data2[i-1]
else:
    data1=[A[i] for i in range(0,N)]
    for i in range(1,N):
        data1[-i-1]+=data1[-i]

    data2=[A[2*i+1] for i in range(0,N//2)]
    for i in range(1,len(data2)):
        data2[i]+=data2[i-1]

for _ in range(Q):
    x=int(input())
    index=bisect.bisect_right(A,x)
    start=1
    end=N-index
    while end-start>1:
        test=(end+start)//2
        r=N-test-1
        l=bisect.bisect_left(A,2*x-A[-test])
        if r-l+1>=test-1:
            start=test
        else:
            end=test
    r=N-end-1
    l=bisect.bisect_left(A,2*x-A[-end])
    if r-l+1>=end-1:
        m=end
    else:
        m=start
    if m==0:
        m=1
    ans=data1[-m]
    num=(N-2*m+1)//2
    if num>0:
        ans+=data2[num-1]
    print(ans)

Solution (Python):
from bisect import *
import sys
input = sys.stdin.readline
n,q = map(int,input().split())
A = list(map(int,input().split()))
every2 = [[0]*(n//2 + 2) for _ in range(2)]
right = [0]*(n+1)

for i in range(n):
    odd = i&1
    every2[odd][i//2 + 1] = every2[odd][i//2] + A[i]
    right[i+1] = right[i] + A[-i-1]


def ok(y,x):
    M = A[-y]
    if M <= x:return False
    d = M - x
    m = x - d
    return bisect_left(A,m)+2*y-1 <= n

for i in range(q):
    X = int(input())
    W = bisect_right(A,X)
    top = n - W + 1
    bottom = 1
    while top - bottom > 1:
        mid = (top + bottom)//2
        if ok(mid,X):
            bottom = mid
        else:
            top = mid
    ans = right[bottom] + every2[1 - (n&1)][(n-1)//2 + 1 - bottom]
    print(ans)

Solution (Python):
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)

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

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 += acc[N-2*(N-border)]-eacc[N-2*(N-border)]
        else:
            ans += eacc[N-2*(N-border)]
    
    print(ans)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
from bisect import bisect_left
N,Q,*L = map(int, open(0).read().split())
A = L[:N]
S = []
M = []
x = 0
y = 0
m = sum(A)
for i in range(N):
  if i%2==0:
    x += A[i]
    S.append(x)
  else:
    y += A[i]
    S.append(y)
for i in range(N):
  M.append(m)
  m -= A[i]

for q in L[N:]:
  i = bisect_left(A,q)
  if 0<i<N and q-A[i-1]<=A[i]-q:
    i = i-1
  if i>=N-1:
    print(S[N-1])
    continue
  l = -1
  r = N
  while l+1<r:
    s = (l+r)//2
    k = N-1-s
    if s<=i:
      l = s
      continue
    x = s-i+1
    if x>k:
      r = s
      continue
    y = k-x
    m = i-y-1
    if m<0:
      l = s
      continue
    if q-A[m]<=A[s]-q:
      r = s
    else:
      l = s
  a = M[r]
  cnt = N-r
  cnt -= r-i-1
  b = i-cnt
  if b>=0:
    a += S[b]
  print(a)

Solution (Python):
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])

Solution (Python):
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]

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]
  
  if (ok + 1) * 2 <= N: res += cs2[-1] - cs2[(ok + 1) * 2]
  print(res)

Solution (Python):
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
    
    for query in range(Q):
        x = int(input())
        ok = binary_search(x)
        ans = cum[N] - cum[ok-1]
        t = N - (N-ok+1)*2
        
        if t > 0:
            ans += cum_e[t//2]
        print(ans)


if __name__ == '__main__':
    main()