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:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, Q = LI()
    A = LI()
    X = [I() for _ in range(Q)]
    S = [0]*(N+1)
    S_odd = [0]*(N+1)
    S_even = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i] + A[i]
        S_odd[i+1] = S_odd[i] + A[i] * (i%2==0)
        S_even[i+1] = S_even[i] + A[i] * (i%2==1)

    ans = [0]*Q
    L = [inf]*N
    for i in range(N-1):
        if i==0:
            L0 = -inf
        else:
            L0 = A[i-1]
        R0 = i + (N-i)//2
        L[i] = L0+R0-1
    #print(L)
    #print(S)
    #print(S_odd)
    #print(S_even)

    def calc_score(l,r):
        rep = S[N] - S[r]
        if (N-r-1)>r-l:
            if l%2==1:
                rep += S_odd[l-1]
            else:
                rep += S_even[l-1]
        else:
            if l%2==1:
                rep += S_even[l-1]
            else:
                rep += S_odd[l-1]
        #print(rep)
        return rep

    for q in range(Q):
        #print(X[q])
        i = bisect.bisect_right(L,X[q])
        #print(i,i + (N-i-1)//2)
        ans[q] = calc_score(i,i + (N-i-1)//2)

    for v in ans:
        print(v)
    return

def examE():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    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 _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)


    def calc_takahasi_top_n(x):
        # x - span <= k <= x + span なる k 軸 x 中心とした幅 span の区間を考える
        # この区間に含まれる L の要素の個数が、それよりも右側の要素の個数と一致 or 1 個少ない場合求める span である
        left = 0
        right = 10 ** 9
        while True:
            mid = (left + right) // 2
            aoki = bisect_right(L, x + mid) - bisect_left(L, x - mid)
            takahashi = n - bisect_right(L, x + mid)
            if aoki == takahashi or aoki == takahashi - 1:
                return takahashi
            elif aoki == takahashi + 1:
                return takahashi + 1
            elif aoki > takahashi + 1:
                right = mid
            else:
                left = mid



    def solve(x):
        top_n = calc_takahasi_top_n(x)
        res = max(0, n - top_n * 2)
        # debug(f'top_n {top_n}')
        # debug(f'res {res}')
        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):
        if i > 0:
            rev_acum[i] += rev_acum[i-1]
    skip_sum = [0] + L[:]
    for i in range(n):
        if i > 1:
            skip_sum[i] += skip_sum[i-2]
    # debug(rev_acum)
    # debug(skip_sum)

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    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 _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)


    def calc_takahasi_top_n(x):
        # x - span <= k <= x + span なる k 軸 x 中心とした幅 span の区間を考える
        # この区間に含まれる L の要素の個数が、それよりも右側の要素の個数と一致 or 1 個少ない場合求める span である
        left = 0
        right = 10 ** 9
        while True:
            mid = (left + right) // 2
            aoki = bisect_left(L, x + mid) - bisect_left(L, x - mid)
            takahashi = n - bisect_left(L, x + mid)
            if aoki == takahashi or aoki == takahashi - 1:
                return takahashi
            elif aoki > takahashi:
                right = mid
            else:
                left = mid        



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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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)]

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 = sum(A)+100
for x in X:
    if x > (A[-1]+A[-2])//2:
        print(T[-1])
        exit()
    high = maxhigh
    low = 0
    R = high
    ans = 0
    while True:
    #for i in range(20):
        l = x-R
        r = x+R
        li = bisect.bisect_left(A,l)
        ri = bisect.bisect_right(A,r)
        M = ri-li
        if ri == N-M:
            #print("A")
            if li > 0:
                ans += T[li-1]
            break
        if ri == N-M-1:
            #print("B")
            #ans += A[ri]
            li -= 1
            if li > 0:
                ans += T[li-1]
            break
        if ri == N-M-2:
            #print("C")
            #ans += A[ri]
            #ans += A[ri+1]
            li -= 2
            if li > 0:
                ans += T[li-1]
            break
        if ri < N-M-2:
            low = R
            R = (R+high)//2
        elif N-M < ri:
            high = R
            R = (R+low)//2
        #print(low,high,ri, N-M,",",R,x)
    if ri > 0:
        ans += S[N-1] - S[ri-1]
    else:
        ans += S[N-1]
    print(ans)

Submission status: Wrong Answer

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)]

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()

for x in X:
    if x > (A[-1]+A[-2])//2:
        print(T[-1])
        exit()
    R = A[-1] + 1
    high = R
    low = 0
    #while True:
    ans = 0
    for i in range(20):
        l = x-R
        r = x+R
        li = bisect.bisect_left(A,l)
        ri = bisect.bisect_right(A,r)
        M = ri-li
        if ri == N-M:
            #print("A")
            if li > 0:
                ans += T[li-1]
            break
        if ri == N-M-1:
            #print("B")
            #ans += A[ri]
            li -= 1
            if li > 0:
                ans += T[li-1]
            break
        if ri == N-M-2:
            #print("C")
            #ans += A[ri]
            #ans += A[ri+1]
            li -= 2
            if li > 0:
                ans += T[li-1]
            break
        if ri < N-M-2:
            low = R
            R = (R+high)//2
        elif N-M < ri:
            high = R
            R = (R+low)//2
        #print(low,high,ri, N-M,",",R,x)
    if ri > 0:
        ans += S[N-1] - S[ri-1]
    else:
        ans += S[N-1]
    print(ans)

Submission status: Wrong Answer

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)]

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()

for x in X:
    R = A[-1] + 1
    high = R
    low = 0
    while True:
        l = x-R
        r = x+R
        #ii = bisect.bisect_left(A,x)
        li = bisect.bisect_right(A,l)
        ri = bisect.bisect_right(A,r)
        M = ri-li
        #print(l,r,li,ri,M)
        if ri < N-M - 2:
            low = R
            R = (R+high)//2 + 1
        elif N-M < ri:
            high = R
            R = (R+low)//2
        else:
            break
    ans = 0
    if ri == N-M-2:
        ans += A[ri] + A[ri+1]
        li -= 2
    elif ri == N-M-1: # special case
        ans += A[ri]
        li -= 2
    #print(N-M,li)
    ans += S[N-1] - S[N-M-1]
    if li > 0:
        ans += T[li-1]
    print(ans)

Submission status: Wrong Answer

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)]

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()

for x in X:
    R = A[-1] + 1
    high = R
    low = 0
    #while True:
    for j in range(10):
        l = x-R
        r = x+R
        #ii = bisect.bisect_left(A,x)
        li = bisect.bisect_right(A,l)
        ri = bisect.bisect_right(A,r)
        M = ri-li
        #print(l,r,li,ri,M)
        if ri < N-M - 2:
            low = R
            R = (R+high)//2 + 1
        elif N-M < ri:
            high = R
            R = (R+low)//2
        else:
            break
    ans = 0
    if ri == N-M-2:
        ans += A[ri] + A[ri+1]
        li -= 2
    elif ri == N-M-1: # special case
        ans += A[ri]
        li -= 2
    #print(N-M,li)
    ans += S[N-1] - S[N-M-1]
    if li > 0:
        ans += T[li-1]
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
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


# @mt
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 = min(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()

Submission status: Wrong Answer

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)
        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 = w[-1]-w[ri-1]
    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: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

m = N // 2
res = [sum(A[m:])] * 2
idx = []
if N % 2 == 1:
    for i in range(m):
        x = res[-1] + A[i * 2] - A[i + m]
        res.append(x)
    for i in range(m + 1):
        x = A[N - i - 2]
        y = A[N - i - 3]
        idx.append((x + y) // 2)
else:
    for i in range(m - 1):
        x = res[-1] + A[i * 2 + 1] - A[i + m]
        res.append(x)
    for i in range(m):
        x = A[N - i - 2]
        y = A[N - i - 3]
        idx.append((x + y) // 2)
idx.reverse()

for i, x in enumerate(X):
    print(res[bisect.bisect_left(idx, x)])

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split())) + [10 ** 10]
cs = [0] * (N + 1)
csd = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]
for i in range(N - 1, -1, -2): csd[i + 1] = a[i]
for i in range(N): csd[i + 1] += csd[i]

#print(cs)
#print(csd)

for _ in range(Q):
  x = int(input())
  i = bl(a, x)
  if abs(a[i - 1] - x) <= abs(a[i] - x): i -= 1
  i = min(N - 2, i)
  if N - i <= -(-N // 2):
    print(cs[-1] - cs[min(N, i + 1)] + csd[i])
  else:
    print(cs[-1] - cs[N // 2])

Submission status: Wrong Answer

Solution code:
import copy
n, q = map(int,input().split())
b = [int(i) for i in input().split()]
b.sort()
for i in range(q):
    ans = 0
    a = copy.deepcopy(b)
    #print(a)
    x = int(input())
    while len(a) > 1:
        tmp=a[len(a) - 1]
        #print(ans, a[len(a) - 1])
        ans += a[len(a) - 1]
        del a[len(a)-1] #高橋くん
        l = 0
        r = len(a) - 1
        while r - l > 1:
            c = (l + r) // 2
            if a[c] >= x:
                r = c
            elif a[c] < x:
                l = c + 1
        if abs(a[r] - x) < abs(a[l] - x):
            l = r
        tmp2 = a[l]
        del a[l] #青木くん
        #print(a, l, r, tmp, tmp2)
    if len(a) == 1:
        ans += a[0]
    print(ans)

Submission status: Wrong Answer

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

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]
            even[i] += even[i - 1]
        else:
            odd[i] += odd[i - 1]
            even[i] += even[i - 1] + a[i]
    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
        l = ng - n - ng
        ok -= 1
        ans = acc[-1] - acc[ok]
        if l < 0:
            pass
        elif n & 1:
            ans += odd[l]
        else:
            ans += even[l]
        print(ans)
        
    return


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