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:
import bisect
n, q = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
cuma = [0] * (n+1)
bipartite_cuma = [0] * (n+2)
for i in range(0, n):
    cuma[i+1] = cuma[i] + a[i]
    bipartite_cuma[i+2] = bipartite_cuma[i] + a[i]
for i in range(q):
    x = int(input())
    l = bisect.bisect_left(a, x) - 2
    l = max(l, 0)
    r = n
    while r - l > 1:
        mid = (l + r) // 2
        t_turn = n - mid
        a_lower_value = x - (a[mid] - x)
        a_turn = mid - bisect.bisect_left(a, a_lower_value) + 1
        if a_turn >= t_turn:
            r = mid
        else:
            l = mid
    ll = bisect.bisect_left(a, x - (a[l] - x))
    if ll > l:
        ll = l
    if n -1 - l <= l+1 - ll:
        takahashi = cuma[n] - cuma[l+1] + bipartite_cuma[ll+1]
        aoki = cuma[l+1] - cuma[ll] + bipartite_cuma[ll]
    else:
        takahashi = cuma[n] - cuma[l+1] + bipartite_cuma[ll]
        aoki = cuma[l+1] - cuma[ll] + bipartite_cuma[ll+1]
    print(takahashi)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def s_list(): return list(input())
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]#NumberGrid
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]


if __name__ == '__main__':
    n, q = wi()
    A = wi()
    X = hi(q)

    accu_a = list(accumulate(A))
    # from_zero_sum = [i for idx, i in enumerate(a) if idx % 2 == 0]
    # from_one_sum = [i for idx, i in enumerate(a) if idx % 2 == 1]


    # 単調性のある関数の解を見つける

    def isOK(mid):
        turn = n - 1 - mid
        d = mid + 1
        c = mid
        b = c - turn + 2
        a = b - 1
        if b < 0:
            return "f", "t"

        if abs(A[a] - x) < abs(A[c] - x) and a >= 0:
            a -= 1
            if abs(A[a] - x) < abs(A[c] - x) and a >= 0:
                return "t", "t"
            return "d", "t"
        elif abs(A[b] - x) > abs(A[d] - x):
            return "f", "a"
        else:
            return "d", "t"

    # 汎用的な二分探索のテンプレ
    # 条件を満たす最小値（ng,ok）
    def binary_search():
        ng = -1  # 「index = 0」が条件を満たすこともあるので、初期値は -1
        ok = len(A)  # 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

        # ok と ng のどちらが大きいかわからないことを考慮
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2

            B = isOK(mid)

            if B[0] == "t":
                ok, t_or_a = mid, B[1]
            elif B[0] == "f":
                ng, t_or_a = mid, B[1]
            else:
                ok, t_or_a = mid, B[1]
                return ok, t_or_a
        return ok, t_or_a

    for _, x in enumerate(X):
        # r_b = bisect_right(A, x)
        ok, t_or_a = binary_search()
        ans += accu_a[-1] - accu_a[ok]
        turn = n - 1 - ok
        b = ok - turn + 2

        if t_or_a == "t":
            b -= 2
        for i in range(b, -1, -2):
            ans += A[i]
        print(ans)
        ans = 0

Submission status: Wrong Answer

Solution code:
import bisect
n, q = map(int, input().split())
a_list = list(map(int, input().split()))
xnum = [0]*q
for i in range(q):
    xnum[i] = int(input())

card = sorted(a_list)

for x in xnum:
    xpos = bisect.bisect(card, x)
    cnt = 0
    upos = 0
    lpos = 1
    for i in range(1, n+1):
        if i + upos >= n-xpos:
            break
        if xpos-lpos < 0 or abs(card[xpos+upos] - x) < abs(card[xpos-lpos] - x):
            upos += 1
        else:
            lpos += 1
    print(sum(card[-i:]) + (sum(card[:n-2*i][::-2]) if 2*i < n else 0))

Submission status: Wrong Answer

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]
    d = [i for i in range(n)]
    for i in range(q):
        x = I()
        d.sort()
        d.sort(key = lambda y:abs(x-a[y]))
        l = 0
        r = n
        while r-l > 1:
            m = (l+r)//2
            k = d.index(m)
            if n-k > m:
                l = m
            else:
                r = m
        k = d.index(l)
        r = l-k
        if k == n-1-l:
            l -= 1
        ans = b[n-1]-b[l]
        j = r-1
        if j >= 0:
            if n%2:
                ans += b[j]-c[j]
            else:
                ans += c[j]
        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: Wrong Answer

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])
	#elif n%2 == 0:
	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
		#print(ok)
		print(s[n] - s[n-(ok+1)//2] + oe[n - (ok+1)//2 * 2 - 1])
	#else:
	#	ok = 0
	#	ng = n//2 + 1
	#	while abs(ng-ok) > 1:
	#		mi = (ng+ok) // 2
	#		if abs(x - a[n - 2*mi]) <= abs(x - a[n - mi]):
	#			ok = mi
	#		else:
	#			ng = mi

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left
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
		print(s[n] - s[n-(ok+1)//2] + oe[n - (ok+1)//2 * 2 - 1])

Submission status: Wrong Answer

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
    print pos1, pos2
    ans[index] = S[N] - S[pos2 - 1] + ALT[pos1 - 1]

for a in ans:
    print a

Submission status: Wrong Answer

Solution code:
def gV(list, num):
    import numpy as np
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx
def nea(n,q,a,x):
    aa=a[:]
    taka=0
 
    for z in range(q):
        for i in range(n):
            if a[-i-1]==999999:
                pass
            else:
                taka+=a[-i-1]
                a[-i-1]=999999
                a[gV(a,x[z])]=999999
        print(taka)
        a=aa[:]
        taka=0

    return 

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left

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

Position = {a: i for i, a in enumerate(A, start=1)}  # 各カードが何番目にあるか
Acc = list(accumulate(A))
if N % 2 == 0:
    Cross = list(accumulate([(A[i] if i % 2 == 1 else 0) for i in range(N)]))
else:
    Cross = list(accumulate([(A[i] if i % 2 == 0 else 0) for i in range(N)]))

for q in range(Q):
    X = int(input())

    xl = bisect_left(A, X)  # xの入る場所
    xr = bisect_left(A, X + max(0, X - A[xl - 1] + 1))  # 右側臨界
    Aoki_zone = xr - xl  # 青木君はxの右側何枚を取ろうとするか
    than_X = N - xl  # xの右側に何枚あるか

    # 被る地点を調整
    if xl + Aoki_zone <= Position[A[xr - 1]]:
        Aoki_zone = max(0, Aoki_zone - 1)
    Takahashi_zone = min(max(1, than_X - Aoki_zone), N - N // 2)  # 結局高橋君は上から何枚とるか

    ans = 0
    ans += Acc[-1] - Acc[N - Takahashi_zone - 1]
    if Takahashi_zone < N - N // 2:
        ans += Cross[N - 2 * Takahashi_zone - 1]

    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left

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

Acc = list(accumulate(A))
if N % 2 == 0:
    Cross = list(accumulate([(A[i] if i % 2 == 1 else 0) for i in range(N)]))
else:
    Cross = list(accumulate([(A[i] if i % 2 == 0 else 0) for i in range(N)]))

for q in range(Q):
    X = int(input())

    xl = bisect_left(A, X)  # xの入る場所
    Aoki_zone = bisect_left(A, X + max(0, X - A[xl - 1])) - xl  # 青木君はxの右側何枚を取ろうとするか
    than_X = N - xl  # xの右側に何枚あるか
    Takahashi_zone = min(max(1, than_X - Aoki_zone), N - N // 2)  # 結局高橋君は上から何枚とるか

    ans = 0
    ans += Acc[-1] - Acc[N - Takahashi_zone - 1]
    if Takahashi_zone < N - N // 2:
        ans += Cross[N - 2 * Takahashi_zone - 1]

    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys

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

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

if N == 2:
    print(As[-1])
    sys.exit()

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

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

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

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

Submission status: Wrong Answer

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


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

    def __len__(self):
        return self.n

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


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

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


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

# x <= A[i]


def nankaime(x, i):
    return i - index_left(x, i) + 1


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


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


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


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

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
X = [0] * Q

accAll = [0] * N
accAll[0] = A[0]
accEven = [0] * N
accEven[0] = A[1]
accOdd = [0] * N
accOdd[0] = A[0]
for i in range(N-1):
    accAll[i+1] = accAll[i] + A[i+1]
    if i % 2 == 1 and i < (N-2):
        accEven[(i+1)//2] =  accEven[i//2] + A[i+2]
    if i % 2 == 0 and i < (N-2):
        accOdd[(i+2)//2] = accOdd[i//2] + A[i+2]

tk_num = N // 2 if N % 2 == 0 else (N // 2) + 1
for i in range(Q):
    X[i] = int(input())
    ng,ok = -1,N
    while abs(ok-ng) > 1:
        mid = (ok + ng) // 2
        if X[i] <= A[mid]:
            ok = mid
        else:
            ng = mid

    if (ok < N and ok > 0 and (A[ok]-X[i]) < (X[i]-A[ok-1])):
        ok += 1

    tk_get = N-ok
    ## 大きい順に全部取れる
    if tk_get >= tk_num:
        print(accAll[N-1]-accAll[N-1-tk_num])
    else:
        board = (N-1-tk_get*2)
        if (board % 2 == 0):
            print(accAll[N-1] - accAll[N-1-tk_get] + accOdd[board//2])
        else:
            print(accAll[N-1] - accAll[N-1-tk_get] + accEven[board//2])

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
X = [0] * Q

accAll = [0] * N
accAll[0] = A[0]
accEven = [0] * N
accEven[0] = A[1]
accOdd = [0] * N
accOdd[0] = A[0]
for i in range(N-1):
    accAll[i+1] = accAll[i] + A[i+1]
    if i % 2 == 1 and i < (N-2):
        accEven[(i+1)//2] =  accEven[i//2] + A[i+2]
    if i % 2 == 0 and i < (N-2):
        accOdd[(i+2)//2] = accOdd[i//2] + A[i+2]

tk_num = N // 2 if N % 2 == 0 else (N // 2) + 1
for i in range(Q):
    X[i] = int(input())
    ng,ok = -1,N
    while abs(ok-ng) > 1:
        mid = (ok + ng) // 2
        if X[i] < A[mid]:
            ok = mid
        else:
            ng = mid

    if (ok < N and ok > 0 and (A[ok]-X[i]) < (X[i]-A[ok-1])):
        ok += 1

    tk_get = N-ok
    ## 大きい順に全部取れる
    if tk_get >= tk_num:
        print(accAll[N-1]-accAll[N-1-tk_num])
    else:
        board = (N-1-tk_get*2)
        if (board % 2 == 0):
            print(accAll[N-1] - accAll[ok-1] + accOdd[board//2])
        else:
            print(accAll[N-1] - accAll[ok-1] + accEven[board//2])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def main():
    n, q = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))

    alt_sum_1 = [0]
    alt_sum_2 = [0]
    pref_sums = [0]
    for i in range(n):
        if i % 2 == 0:
            alt_sum_1.append(alt_sum_1[-1] + a[i])
        else:
            alt_sum_2.append(alt_sum_2[-1] + a[i])
        pref_sums.append(pref_sums[-1] + a[i])

    for _ in range(q):
        x = int(input())
        lo, hi = 0, 10**9 + 1
        while lo < hi:
            mi = (lo + hi) // 2
            left, right = bisect_left(a, x - mi), bisect_left(a, x + mi)

            if right - left >= len(a) - right - (n % 2):
                hi = mi
            else:
                lo = mi + 1

        left, right = bisect_left(a, x - lo), bisect_left(a, x + lo)
        x = pref_sums[-1] - pref_sums[right]

        if right - left == len(a) - right:
            if left % 2 == 0:
                x += alt_sum_2[left // 2]
            else:
                x += alt_sum_1[(left + 1) // 2]
        else:
            if left % 2 == 0:
                x += alt_sum_1[left // 2]
            else:
                x += alt_sum_2[(left - 1) // 2]

        print(x)


if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
A = list(map(int, input().split()))
A_new = [list()] * Q
result = [0] * Q

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

for i in range(Q):
    A_new[i] = A[:]
    
    while A_new[i]:
        result[i] = result[i] + A_new[i].pop()
        if A_new[i]:
            state = 0
            for j in range(x):
                if x - j in A_new[i]:
                    A_new[i].remove(x - j)
                    state = 1
                    break
                if x + j in A_new[i]:
                    A_new[i].remove(x + j)
                    state = 1
                    break          
            if state == 0:
                del A_new[i][0]

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def main():
    n, q = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))

    alt_sum_1 = [0]
    alt_sum_2 = [0]
    pref_sums = [0]
    for i in range(n):
        if i % 2 == 0:
            alt_sum_1.append(alt_sum_1[-1] + a[i])
        else:
            alt_sum_2.append(alt_sum_2[-1] + a[i])
        pref_sums.append(pref_sums[-1] + a[i])

    print(alt_sum_1, alt_sum_2)

    for _ in range(q):
        x = int(input())
        lo, hi = 0, 10**9 + 1
        while lo < hi:
            mi = (lo + hi) // 2
            left, right = bisect_left(a, x - mi), bisect_left(a, x + mi)

            if right - left >= len(a) - right - (n % 2):
                hi = mi
            else:
                lo = mi + 1

        left, right = bisect_left(a, x - lo), bisect_left(a, x + lo)
        x = pref_sums[-1] - pref_sums[right]

        if right - left == len(a) - right:
            if left % 2 == 0:
                x += alt_sum_2[left // 2]
            else:
                x += alt_sum_1[(left + 1) // 2]
        else:
            if left % 2 == 0:
                x += alt_sum_1[left // 2]
            else:
                x += alt_sum_2[(left - 1) // 2]

        print(x)


if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Wrong Answer

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