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:
#!/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 l & 1:
            ans += odd[l]
        else:
            ans += even[l]
        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):
        y = n - mid - 1
        if y == 0:
            return False
        al = n - 2 * y
        if al < 0:
            return True
        return abs(a[mid] - x) < abs(a[al] - 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 l & 1:
            ans += odd[l]
        else:
            ans += even[l]
        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):
        y = n - mid - 1
        if y == 0:
            return False
        al = n - 2 * y
        if al < 0:
            return True
        return abs(a[mid] - x) < abs(a[al] - 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
        y = n - ok - 1
        al = n - 2 * y - 1
        ans = acc[-1] - acc[ok]
        if al < 0:
            pass
        elif al & 1:
            ans += odd[al]
        else:
            ans += even[al]
        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):
        y = n - mid - 1
        if y == 0:
            return False
        al = n - 2 * y
        if al < 0:
            return True
        return abs(a[mid] - x) < abs(a[al] - 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()
        x_index = bisect_right(a, x)
        if x_index >= n:
            if n & 1:
                print(even[-1])
            else:
                print(odd[-1])
        elif x_index <= 0:
            print(acc[-1] - acc[n // 2 - 1])
        else:
            if abs(a[x_index - 1] - x) <= abs(a[x_index] - x):
                x_index -= 1
            ok = x_index
            ng = n
            while abs(ng - ok) > 1:
                mid = (ok + ng) // 2
                if f(mid):
                    ok = mid
                else:
                    ng = mid
            y = n - ok - 1
            al = n - 2 * y - 1
            ans = acc[-1] - acc[ok]
            if al < 0:
                pass
            elif al & 1:
                ans += odd[al]
            else:
                ans += even[al]
            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):
        y = n - mid - 1
        if y == 0:
            return False
        al = n - 2 * y
        if al < 0:
            return True
        if abs(a[mid] - x) > abs(a[al] - x) and abs(a[mid] - x) < abs(a[al - 1] - x):
            return True
        return False
    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()
        x_index = bisect_right(a, x)
        if x_index >= n:
            if n & 1:
                print(even[-1])
            else:
                print(odd[-1])
        elif x_index <= 0:
            print(acc[-1] - acc[n // 2 - 1])
        else:
            if abs(a[x_index - 1] - x) <= abs(a[x_index] - x):
                x_index -= 1
            ok = x_index
            ng = n
            while abs(ng - ok) > 1:
                mid = (ok + ng) // 2
                if f(mid):
                    ok = mid
                else:
                    ng = mid
            y = n - ok - 1
            al = n - 2 * y - 1
            ans = acc[-1] - acc[ok]
            if al < 0:
                pass
            elif al & 1:
                ans += odd[al]
            else:
                ans += even[al]
            print(ans)
            
    return


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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

oddSum = [0] * (N + 1)
evenSum = [0] * (N + 1)
accA = [0] * (N + 1)

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

def calcAokiIndex(x):
    aoki = bisect_left(A, x)
    if abs(x - A[aoki]) >= abs(x - A[aoki - 1]):
        aoki -= 1

    taka = N - 1
    while taka - aoki > 1:
        mid = (taka + aoki) // 2
        lowerAoki = bisect_left(A, x - abs(A[mid] - x))
        cnt = mid - lowerAoki + 1
        if N - mid <= cnt:
            taka = mid
        else:
            aoki = mid

    return aoki

ans = []
M = A[-1]

for x in X:
    if x >= M:
        ans.append(oddSum[N] if N % 2 == 1 else evenSum[N])
        continue

    aoki = calcAokiIndex(x)
    lowerAoki = bisect_left(A, x - abs(A[aoki] - x))
    cnt = aoki - lowerAoki + 1

    taka = accA[N] - accA[aoki + 1]

    if cnt == N - aoki - 1:
        taka += (oddSum[lowerAoki] if lowerAoki % 2 == 1 else evenSum[lowerAoki])
    else:
        taka += (oddSum[lowerAoki] if lowerAoki % 2 == 0 else evenSum[lowerAoki])

    ans.append(taka)

print(*ans, sep='\n')

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()))
cs = [0] * N
cs2 = [0] * N
cs[0] = a[0]
cs2[-1] = a[-1]
table = [0] * (N + 1)
for i in range(N - 1):
  cs[i + 1] = cs[i] + a[i + 1]
for i in range(N - 1, -1, -2):
  if i - 1 >= 0: cs2[i - 1] = cs2[i]
  if i - 2 >= 0: cs2[i - 2] = cs2[i] + a[i - 2]
for i in range(N + 1):
  if i < N // 2:
    table[i] = cs[-1] - cs[N // 2 - 1]
  elif i <= N - 2:
    #print(i, cs[-1] - cs[i], - cs2[i] + cs2[0])
    table[i] = cs[-1] - cs[i] - cs2[i] + cs2[0]
    #if (-(-N // 2) - (N - i - 1)) > 1: table[i] -= cs2[(-(-N // 2) - (N - i - 1)) * 2 - 1]
  else:
    table[i] = table[i - 1]
"""
print(table)
print()
print(cs)
print(cs2)
"""
for _ in range(Q):
  q = int(input())
  l = bl(a, q) - 1
  r = min(bl(a, q), N - 1)
  x = r
  if l >= 0:
    if abs(a[l] - q) == abs(a[r] - q):
      x = l
  print(table[x])

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
a = list(map(int,input().split()))
g = [0]*(n+1)
h = [0] + a[1-n%2::2]
m = len(h)-1
for i in range(n):
  g[i+1] = g[i] + a[i]
for i in range(m):
  h[i+1] += h[i]
d = {10**10:h[-1]}
for j in range(1,(n+1)//2+1):
  tak = g[n] - g[n-j] + h[(n-2*j)//2+n%2]
  key = (a[n-j]+a[n-2*j])//2 + 1
  d[key] = tak
l = list(d.keys())
l.sort()
m = len(l)
l.append(0)
d[0] = g[n]-g[n-(n+1)//2]

for _ in range(q):
  x = int(input())
  ok,ng = m,-1
  while ok-ng>1:
    mid = (ng+ok)//2
    if l[mid] >= x:
      ok = mid
    else:
      ng = mid
  print(d[l[ok]])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

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

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

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

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

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

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

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

    flag = False
    if right1 != right2:
        flag = True
    ans = left_sum[N-right2]

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

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

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

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

if N==2:
    print(A[-1])
    exit()

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

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

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

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

    flag = False
    if right1 != right2:
        flag = True
    
    ans = left_sum[N-right2]

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

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

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

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

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

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

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

    left = 0
    right = N//2 + 1
    while (right-left>1):
        mid = left + (right-left)//2
        if abs(A[N-mid-1]-x)<abs(A[N-2*mid-1]-x):
            right = mid
        else:
            left = mid
    right2 = right
    
    flag = False
    if right1 != right2:
        flag = True
    
    ans = left_sum[N-right2]
    
    if flag:
        if N-right1-right2-2>=0:
            ans += sum_list[N-right1-right2-2]
    else:
        if N-right1-right2-1>=0:
            ans += sum_list[N-right1-right2-1]
    print(ans)

Submission status: Wrong Answer

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

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

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


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 lr(x, cnt):
    # x に近いのを cnt 個取ったときのインデックス [l, r)
    def fn(l):
        r = l + cnt - 1
        dr = A[r] - x
        dl = x - A[l]
        return dr - dl

    l = bleft(fn, 0, lo=0, hi=N - cnt)
    l = bleft(fn, -fn(l), 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: Wrong Answer

Solution code:

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

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

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

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

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

		t = (loc_min + loc_max) // 2


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

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

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

Submission status: Wrong Answer

Solution code:

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

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

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

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

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

		t = (loc_min + loc_max) // 2


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

			if 2*t - N - 1 >= 0 and A[t - 1] - x >= x - A[2*t - N - 1]:
				loc_max = t - 1

			elif A[t] - x < x - A[2*t - N]:
				loc_min = t + 1
			else:
				break

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

Submission status: Wrong Answer

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

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

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

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

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

		# t は中央番目の数
		t = (loc_min + loc_max) // 2

		while (loc_min <= loc_max):

			if 2*t - N - 1 >= 0 and A[t - 1] - x >= x - A[2*t - N - 1]:
				loc_max = t - 1

			elif A[t] - x < x - A[2*t - N]:
				loc_min = t + 1
			else:
				break
			#print(loc_min, loc_max, t)
			t = (loc_min + loc_max) // 2
		ans = sum_list[-1] - sum_list[t] + even_odd_sum[2*t - N - 1 + 2]
		print(ans)

Submission status: Wrong Answer

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

from bisect import bisect_left

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

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

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

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

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

Submission status: Wrong Answer

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

    print(taka_sum)

Submission status: Wrong Answer

Solution code:
import bisect
INF = 10**9
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)
for i in range(q):
    # Get div of aoki - takahashi
    x = int(input())
    big = bisect.bisect_left(a, x)
    small = big - 1
    if (x - a[small]) ** 2 <= (x - a[big]) ** 2:
        l = small
    else:
        l = big
    r = n - 1
    while r - l > 1:
        m = (r + l) // 2
        rng = abs(x - a[m - 1])
        taka = n - m
        aoki = n - taka - (bisect.bisect_left(a, x - rng))
        if 0 <= taka - aoki <= 1:
            r = m
        else:
            l = m
    rng = abs(x - a[r-1])
    taka = n - r
    aoki = n - taka - (bisect.bisect_left(a, x - rng))
    taka_sum = sum_all[n] - sum_all[r]
    aoki_sum = sum_all[r] - sum_all[r - aoki]
    rest = n - taka - aoki
    if taka == aoki:
        if rest % 2 == 0:
            taka_sum += sum_even[rest]
            aoki_sum += sum_odd[rest]
        else:
            taka_sum += sum_odd[rest]
            aoki_sum += sum_even[rest]
    else:
        if rest % 2 == 0:
            aoki_sum += sum_even[rest]
            taka_sum += sum_odd[rest]
        else:
            aoki_sum += sum_odd[rest]
            taka_sum += sum_even[rest]

    print(taka_sum)

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())
    if x > a[-1]:
        x = a[-1]
    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 - 1
        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)