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: Wrong Answer

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

import sys
import bisect
sys.setrecursionlimit(10000)

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

A.sort()
A_COPY = A.copy()

T = []


def takahashi():
    a = A[-1]
    T.append(a)
    del A[-1]


def aoki(x):
    l = bisect.bisect_left(A, x)
    r = bisect.bisect_right(A, x)
    idx = l
    if len(A) > r and len(A) > l:
        if abs(A[l] - x) > abs(A[r] - x):
            idx = r
    if idx == len(A):
        idx -= 1
    del A[idx]


for x in X:
    A = A_COPY.copy()
    T = []
    while True:
        if len(A) == 0:
            break
        takahashi()
        if len(A) == 0:
            break
        aoki(x)
    print(sum(T))

Submission status: Wrong Answer

Solution code:
import copy

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

Xlist = []
sumT = 0

for i in range(Q):
    Xtmp = int(input())
    Xlist.append(Xtmp)
    

for i in range(Q):
    Tlist = []
    A = copy.deepcopy(Alist)
    Adifflist = []


    if Xlist[i] <= A[0]:
        a = len(A)//2
        print(sum(A[a:]))


    
    elif A[-1] <= Xlist[i]:
        for s in range(len(A)):
            if s % 2 == 0:
                sumT += A[len(A)-1-s]
        print(sumT)

    
    else:
        for j in range(len(A)):
            Adifflist.append([abs(A[j]-Xlist[i]), A[j]])

        Adifflist.sort(reverse=False)
            
        while 1:
            Ttmp = A.pop(-1)
            Tlist.append(Ttmp)

            Adifflist.remove([abs(Ttmp-Xlist[i]), Ttmp])

            if A == []:
                print(sum(Tlist))
                break

            Atmp = Adifflist[0][1]
            del Adifflist[0]
            A.remove(Atmp)

            if A == []:
                print(sum(Tlist))
                break

Submission status: Wrong Answer

Solution code:
import itertools
def inpl(): return [int(i) for i in input().split()]

N, Q = inpl()
A = sorted(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())
    if x >= A[-1]:
        print(B[-1])
        continue
    if x <= A[0]:
        print(SA[-1] - SA[N//2-1])
        continue
    if N%2 and abs(A[N//2+1]-x) >= max(abs(A[N//2]-x), abs(A[0]-x)):
        print(SA[-1] - SA[N//2-1])
        continue
    lo = 1
    hi = N//2 + 1
    while hi - lo >1:
        mid = (lo+hi)//2
        if mid > 3:
            t = sorted([abs(x-A[N-mid-1]), abs(x-A[N-mid-2]), abs(x-A[N-2*mid+1]), abs(x-A[N-2*mid])])[1]
            if t > abs(x-A[N-mid]):
                hi = mid
            else:
                lo = mid
            continue
        elif mid == 1:
            if abs(x-A[N-mid-1]) > abs(x-A[N-mid]):
                hi = mid
            else:
                lo = mid
            continue
        elif mid == 2:
            if min(abs(x-A[N-mid-1]), abs(x-A[N-2*mid])) > abs(x-A[N-mid]):
                hi = mid
            else:
                lo = mid
            continue
        else:
            t = sorted([abs(x-A[N-4]), abs(x-A[N-5]), abs(x-A[N-6])])[1]
            if t > abs(x-A[N-3]):
                hi = mid
            else:
                lo = mid
    print(SA[N-1] - SA[N-lo-1] + B[-((2*lo-N)//2)])

Submission status: Wrong Answer

Solution code:
import itertools
import sys
def inpl(): return [int(i) for i in input().split()]

N, Q = inpl()
A = sorted(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())
    if x >= A[-1]:
        print(B[-1])
        continue
    if x <= A[0]:
        print(SA[-1] - SA[N//2-1])
        continue
    if N%2 and abs(A[N//2+1]-x) >= max(abs(A[N//2]-x), abs(A[0]-x)):
        print(SA[-1] - SA[N//2-1])
        continue
    lo = 1
    hi = N//2 + 1
    while hi - lo >1:
        mid = (lo+hi)//2
        if mid > 3:
            t = sorted([abs(x-A[N-mid-1]), abs(x-A[N-mid-2]), abs(x-A[N-2*mid+1]), abs(x-A[N-2*mid])])[1]
            if t > abs(x-A[N-mid]):
                hi = mid
            else:
                lo = mid
            continue
        elif mid == 1:
            if abs(x-A[N-mid-1]) > abs(x-A[N-mid]):
                hi = mid
            else:
                lo = mid
            continue
        elif mid == 2:
            if max(abs(x-A[N-mid-1]), abs(x-A[N-2*mid])) > abs(x-A[N-mid]):
                hi = mid
            else:
                lo = mid
            continue
        else:
            t = sorted([abs(x-A[N-4]), abs(x-A[N-5]), abs(x-A[N-6])])[1]
            if t > abs(x-A[N-3]):
                hi = mid
            else:
                lo = mid
    print(SA[N-1] - SA[N-lo-1] + B[-((2*lo-N)//2)])

Submission status: Wrong Answer

Solution code:
from bisect import bisect
readline = open(0).readline
N, Q = map(int, readline().split())
*A, = map(int, readline().split())
mi = A[0]; ma = A[-1]

def check(x, mid):
    p = bisect(A, x-mid-1)
    q = bisect(A, x+mid)
    return q-p <= N-q+1

def solve(x):
    left = 0; right = max(ma - x, x - mi) + 1
    while left+1 < right:
        mid = (left + right) >> 1
        if check(x, mid):
            left = mid
        else:
            right = mid

    L = left
    p = bisect(A, x-L-1)
    q = bisect(A, x+L)
    c = q-p
    res = 0
    assert q-p <= N-q+1
    if q-p > N-q:
        res += T[N] - T[q-1]
        t = 1
    elif q-p == N-q:
        res += T[N] - T[q]
        t = 0
    else:
        res += T[N] - T[q]
        t = 1
    if t:
        if p > 1:
            res += S[p-1]
    else:
        res += S[p]
    return res

S = [0]*(N+1)
T = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i-1] + A[i] if i >= 1 else A[i]
    T[i+1] = T[i] + A[i]
ans = []
for i in range(Q):
    x = int(readline())
    ans.append("%d\n" % solve(x))
open(1, 'w').writelines(ans)

Submission status: Time Limit Exceeded

Solution code:
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] # right
A = [2*a for a in A] # left
X = [2*x for x in X]

S = list(accumulate(A))
T0 = accumulate(A[::2])
T1 = accumulate(A[1::2])
T = list(reduce(lambda x,y : x+y, zip_longest(T0,T1)))
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)
        #print(l,r,li,ri)
        M = ri-li
        if ri == N-M:
            if li > 0:
                ans += T[li-1]
            break
        if ri == N-M-1:
            #print("HER",li,ri)
            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
        #print(l,x,r,li,ri,OK,"R",R,NG)
    #print(l,x,r,li,ri,OK,R,NG)
    if ri > 0:
        ans += S[N-1] - S[ri-1]
    else:
        ans += S[N-1]
    print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
import copy

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

for i in range(Q):
    x = int(input())
    score = 0

    while len(A) > 0:
        score += A.pop()
        if len(A) > 0:
            i = bisect(A, x)
            if i == 0:
                A.pop(0)
            elif i == len(A):
                A.pop()
            else:
                if x - A[i-1] <= A[i] - x:
                    A.pop(i-1)
                else:
                    A.pop(i)
        else:
            break

    print(score)
    A = copy.copy(B)

Submission status: Time Limit Exceeded

Solution code:
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)
        ri2 = bisect.bisect_left(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 ri != ri2:
            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 = w[-1]-w[ri-1]
    print(r,l,x-m,x+m,li,ri)
    if (ri-li)%2 == 0:
        d = li-1
        if d >= 0:
            if d%2 == 0:
                count += w1[d]
            else:
                count += w2[d]
    else:
        d = li-2
        if d >= 0:
            if d%2 == 0:
                count += w1[d]
            else:
                count += w2[d]
    dic[x] = count
    print(count)



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

Submission status: Time Limit Exceeded

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]
    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
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]
        
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
    # rまではxより大きくて取れる
#     print("r",  r)
    ans = sum(a[r:])
    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)))

Submission status: Time Limit Exceeded

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]
    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 = 0
    r = n-1
    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)))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
cum1 = [0] * N
cum1[0], cum1[1] = A[0], A[1]
for i in range(2, N):
    cum1[i] = cum1[i-2] + A[i]
cum2 = [0] * N
cum2[-1] = A[-1]
for i in range(N-1)[::-1]:
    cum2[i] = cum2[i+1] + A[i]
for _ in range(Q):
    x = int(input())
    lb, ub = 0, 10**9
    while ub - lb > 1:
        m = (lb + ub) // 2
        i = bisect_left(A, x - m)
        j = bisect_right(A, x + m)
        cnt = j - i
        if cnt <= N - j:
            lb = m
        else:
            ub = m
    i = bisect_left(A, x - lb)
    j = bisect_right(A, x + lb)
    i -= (N - j) - (j - i)
    ans = (cum1[i-1] if i > 0 else 0) + (cum2[j] if j < N else 0)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
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]
# ans = [0]*q

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)
# print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
def main():
    # アルメリアさんを参考にした いや全然わからん
    from itertools import accumulate
    from bisect import bisect_left
    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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
A = [int(a) for a in input().split()][::-1]
for _ in range(Q):
    x = int(input())
    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
    l += 1
    print(sum(A[:l] + A[2*l::2]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
A = [int(a) for a in input().split()][::-1]
for _ in range(Q):
    x = int(input())
    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
    l += 1
    print(sum(A[:l] + A[2*l::2]))

Submission status: Time Limit Exceeded

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=nn

    for i,ini in ix:
        l=1
        u=k
        while l+1<u:
            med=(l+u)//2
            if check(med):u=med
            else:l=med+1
        if check(l):k=l
        else:k=u
        ans[i]=aac[-1]-aac[-k-1]+aac2[-k-1]
    for i in ans:
        print(i)
main()

Submission status: Time Limit Exceeded

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]
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))

    for ini in x:
        l=1
        u=min(nn,n-bl(a,ini))
        while l+1<u:
            med=(l+u)//2
            if check(med):u=med
            else:l=med+1
        if check(l):k=l
        else:k=u
        print(aac[-1]-aac[-k-1]+aac2[-k-1])
main()

Submission status: Time Limit Exceeded

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]
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))

    for ini in x:
        l=1
        u=nn
        while l+1<u:
            med=(l+u)//2
            if check(med):u=med
            else:l=med+1
        if check(l):k=l
        else:k=u
        print(aac[-1]-aac[-k-1]+aac2[-k-1])
main()

Submission status: Time Limit Exceeded

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)
            b=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            b=br(a,ini+dist)-bl(a,ini-dist)
        return k>=b

    def b_search(a,b,check):
        while a+1<b:
            med=(a+b)//2
            if check(med):b=med
            else:a=med+1
        if check(a):return a
        else:return b
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))

    for ini in x:
        k=b_search(1,nn,check)
        print(aac[-1]-aac[-k-1]+aac2[-k-1])
main()

Submission status: Time Limit Exceeded

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 b_search(a,b,value):
        while a+1<b:
            med=(a+b)//2
            if value(med):b=med
            else:a=med+1
        if value(a):return a
        else:return b
    
    n,q=map(int,input().split())
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            b=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            b=br(a,ini+dist)-bl(a,ini-dist)
        return k>=b

    for i in x:
        ini=i
        k=b_search(1,n//2+1,check)
        print(aac[-1]-aac[-k-1]+aac2[-k-1])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    def b_search(a,b,value):
        while True:
            med=(a+b)//2
            if a==b:return a
            if a+1==b:
                if value(a):return a
                else:return b
            elif value(med):b=med
            else:a=med+1
    
    n,q=map(int,input().split())
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            b=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            b=br(a,ini+dist)-bl(a,ini-dist)
        return k>=b

    for i in x:
        ini=i
        k=b_search(1,n//2+1,check)
        print(aac[-1]-aac[-k-1]+aac2[-k-1])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    #a,bには下限と上限、valueにはOKな範囲のときはTrue、そうでないときにFalseを返す関数を入れる
    #limは下限を知りたいときはlower、上限を知りたいときはupperを入れる
    def b_search(a,b,value,lim):
        if lim=='upper':
            while True:
                med=(a+b)//2
                if a==b:return a
                elif a+1==b:
                    if value(b):return b
                    else:return a
                elif value(med):a=med
                else:b=med-1
        else:
            while True:
                med=(a+b)//2
                if a==b:return a
                if a+1==b:
                    if value(a):return a
                    else:return b
                elif value(med):b=med
                else:a=med+1
    
    n,q=map(int,input().split())
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            b=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            b=br(a,ini+dist)-bl(a,ini-dist)
        if k>=b:
            return True
        return False

    for i in x:
        ini=i
        k=b_search(1,n//2+1,check,"lower")
        print(aac[-1]-aac[-k-1]+aac2[-k-1])

main()

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
A = list(map(int, input().split()))
Query = [int(input()) for _ in range(Q)]
INF = 10**14

E = [0]
O = [0]
e = 0
o = 0
for i, a in enumerate(A):
    if i % 2 == 0:
        e += a
    else:
        o += a
    E.append(e)
    O.append(o)

S = [0]
s = 0
for a in reversed(A):
    s += a
    S.append(s)

for X in Query:
    ind = N
    if X > A[-1]:
        l = 0
    else:
        l = 0
        r = N+1
        while r-l > 1:
            m = (r+l)//2
            in_left = A[-m]
            in_right = A[-m+m//2-1]
            out_left = A[-m-1] if m < N else -INF
            out_right = A[-m+m//2] if m > 0 else INF
            if X <= out_left:
                l = m
            elif out_right <= X:
                r = m
            else:
                if abs(X-out_left) <= abs(in_right-X):
                    l = m
                elif abs(X-in_left) > abs(out_right - X):
                    r = m
                else:
                    l = m
                    break
    
    ans = S[l-l//2]
    if l%2 != (N-l)%2:
        ans += E[N-l]
    else:
        ans += O[N-l]
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# A = np.random.randint(100, 200, 20)
# A = np.unique(A)
# N = len(A)
# Q = 100
# X = np.random.randint(1, 300, Q)
N, Q = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
X = [int(sys.stdin.readline()) for _ in range(Q)]


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    ret = []
    s = 0
    for a in it:
        s += a
        ret.append(s)
    return ret


# A = np.array(A, dtype=int)
# gt_sum = A[::-1].cumsum()[::-1]
# lt_sum = np.zeros_like(A, dtype=int)
# lt_sum[::2] = A[::2].cumsum()
# lt_sum[1::2] = A[1::2].cumsum()
gt_sum = cumsum(A[::-1])[::-1]
lt_sum = [0] * N
for i, a in enumerate(cumsum(A[::2])):
    lt_sum[i * 2] = a
for i, a in enumerate(cumsum(A[1::2])):
    lt_sum[i * 2 + 1] = a


def test(x):
    a_cp = np.array(A, dtype=float)
    ret = 0
    i_hist = []
    while True:
        if np.any(a_cp < np.inf):
            i = np.argwhere(a_cp < np.inf)[:, 0].max()
            ret += a_cp[i]
            a_cp[i] = np.inf
            i_hist.append(i)
        if np.any(a_cp < np.inf):
            i = abs(a_cp - x).argmin()
            a_cp[i] = np.inf
        else:
            break
    return int(ret)


def bleft(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def tleft(fn, lo, hi):
    # 三分探索
    left = lo
    right = hi
    while abs(right - left) >= 3:
        r1 = (left * 2 + right) // 3
        r2 = (left + right * 2) // 3
        if fn(r1) <= fn(r2):
            right = r2
        else:
            left = r1
    if left + 1 >= hi or fn(left) <= fn(left + 1):
        return left
    if left + 2 >= hi or fn(left + 1) <= fn(left + 2):
        return left + 1
    return left + 2


def lr(x, cnt):
    # x に近いのを cnt 個取ったときのインデックス [l, r)
    def fn(l):
        r = l + cnt - 1
        return max(abs(A[r] - x), abs(A[l] - x))

    l = tleft(fn, lo=0, hi=N - cnt)
    return l, l + cnt


def solve(x):
    if x > A[-2]:
        return lt_sum[N - 1]

    ok = 1
    ng = N // 2 + 1
    while abs(ok - ng) > 1:
        cnt = (ok + ng) // 2
        l1, r1 = lr(x, cnt)
        l2, r2 = N - cnt, N
        if r1 <= l2:
            ok = cnt
        else:
            ng = cnt
    cnt = ok
    l, r = lr(x, cnt)
    if r < N - cnt:
        cnt += 1

    ans = 0
    if 0 <= N - cnt < N:
        ans += gt_sum[N - cnt]
    if 0 <= N - cnt * 2 - 1 < N:
        ans += lt_sum[N - cnt * 2 - 1]
    return ans


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

Submission status: Time Limit Exceeded

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):
    x = int(input())
    # Get div of aoki - takahashi
    # l: aoki takes, r: takahashi takes
    l = 0; r = n - 1
    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]))