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: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
A_list = list(map(int, input().split()))
X_list = [int(input()) for _ in range(Q)]

def taka(cards):
    return max(cards)
def aoki(cards_, x):
    cards = sorted(cards_)
    res = [abs(x-card) for card in cards]
    min_res = min(res)
    for idx, r in enumerate(res):
        if r == min_res:
            return cards[idx]
        
def game(cards, x):
    taka_sum = 0
    while(len(cards)>0):
        taka_card = taka(cards)
        cards.remove(taka_card)
        taka_sum += taka_card
        if len(cards) == 0:
            break
        aoki_card = aoki(cards, x)
        cards.remove(aoki_card)
    return taka_sum

import copy
for X in X_list:
    A_list_copy = copy.copy(A_list) 
    print(game(A_list_copy, X))

Submission status: Time Limit Exceeded

Solution code:
import copy
n, q = [int(i) for i in input().split()]
As = sorted([int(i) for i in input().split()])
for i in range(q):
    x = int(input())
    As_tmp = copy.copy(As)
    As_abs = [abs(a - x) for a in As]
    ans = 0
    # print(As_abs)
    while As_abs:
        ans += As_tmp[-1]
        # print(ans)
        As_tmp.pop(-1)
        As_abs.pop(-1)
        if not As_abs:
            break
        # ans += As[As_abs.index(min(As_abs))]
        idx = As_abs.index(min(As_abs))
        As_tmp.pop(idx)
        As_abs.pop(idx)
        # print(As_abs)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def game(xi, aa):
    first = 0
    second = 0
    i = 0
    while aa:
        if i % 2 == 0:
            first += aa[-1]
            aa.pop(-1)
            i += 1
        else:
            absu = [abs(ai-xi) for ai in aa]
            ind = absu.index(min(absu))
            second += aa[ind]
            aa.pop(ind)
            i += 1
    return(first)


n, q = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
x = []
for i in range(q):
    x.append(int(input()))


for xi in x:
    a_sorted = sorted(a)
    print(game(xi, a_sorted))

Submission status: Time Limit Exceeded

Solution code:
import copy
N,Q = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
a = len(A)
for i in range(Q):
    ans = 0
    X = int(input())
    B = copy.deepcopy(A)
    for j in range(a):
        if j%2 == 0:
            ans += max(B)
            B[B.index(max(B))] = 0
        else:
            count1 = 10**9
            count2 = 0
            for k in range(a):
                if B[k] == 0:
                    continue
                else:
                    if abs(B[k]-X) < count1:
                        count1 = abs(B[k]-X)
                        count2 = k
            B[count2] = 0
    print(ans)

Submission status: Accepted

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



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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
import bisect

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

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

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

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

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

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

        cnt+=1

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

    tmp = cumsum[-1] - cumsum[t_l_ind-1]
    if(a_l_ind>1):
        tmp += cumsum_eo[a_l_ind-1]
    ans.append(tmp)
    # print(ng,ok)

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

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

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

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

Submission status: Accepted

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

def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    s = [0]*(n+1)
    odd = [0]*(n+1)
    even = [0]*(n+1)
    for i in range(n):
        s[i+1] += s[i]+a[i]
        odd[i+1] += odd[i]
        even[i+1] += even[i]
        if i%2:
            odd[i+1] += a[i]
        else:
            even[i+1] += a[i]
    
    key = []
    value = dict()
    v = 0
    for i in range(n):
        if i == n-1:
            k = pow(10, 9)
            key.append(k)
            value[k] = v
            continue
            
        k = (a[i+(n-i)//2]+a[i])//2
        v = s[i+(n-i)//2]-s[i]
        if (n-i)%2:
            if i%2:
                v += even[max(0, i)]
            else:
                v += odd[max(0, i)]
        else:
            if i%2:
                v += odd[max(0, i-1)]
            else:
                v += even[max(0, i-1)]
        
        key.append(k)
        value[k] = v
    
    sum_a = s[n]
    
    for i in range(q):
        x = int(input())
        k = key[bisect.bisect_left(key, x)]
        ans = sum_a-value[k]
        print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    N,Q=MI()
    A=LI()
    if N%2==1:#長さが奇数なら0を足しておく
        A+=[0]
        N+=1
    A.sort()
    
    """
    連続する区間or交互
    """
    
    S=[0]*(N+1)
    S2=[0]*(N+1)#偶数のみ
    
    for i in range(N):
        S[i+1]=S[i]+A[i]
        
    for i in range(0,N-1):
        S2[i+2]=S2[i]+A[i]
        
    # print(S)
    # print(S2)
        
    def calc(P):
        # 先手が上からP枚，後手がその後のP枚をとり，残りを交互に取った時の先手のscore
        fi=S[-1]-S[-P-1]
        fi+=S2[-2*P]
        return fi
    
    def ch(X,P):
        #xが指定され，先手が上からP枚以上取れるか
        maxa=A[-P-1]#後手が取るmax
        mina=A[-2*P+1]#後手がP-1ターン目までに取る取るmin(後手がPターン目に取るものはなんでも良い)
        diff=A[-P]-X
        
        # print(X,P,mina,maxa,diff)
        if diff<0:
            return False
        if X-diff<=mina and maxa<=X+diff:
            return True
        return False
        
    
    for _ in range(Q):
        x=I()
        
        #先手が上から何枚以上取れるか
        ng=N//2 +1
        ok=1#先手が最大値をとる
        while ng-ok>1:
            med=(ok+ng)//2
            if ch(x,med):
                ok=med
            else:
                ng=med
                
        # print(ok)
        print(calc(ok))
            

main()

Submission status: Accepted

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):
        # takahashi がとるカードの左端 ind を求める -> 枚数は n - ind
        left = -1    # これより上
        right = n - 1    # これ以下
        while right - left > 1:
            mid = (left + right) // 2
            # debug(f'{left} {right} {mid}')
            # [n], [n-1], ..., [ind] ととっていく
            takahashi_order = n - mid
            # [x - (A[ind] - x), A[ind]] のカードは全てとっている
            aoki_order = bisect_right(L, L[mid]) - bisect_left(L, x - (L[mid] - x))
            if takahashi_order <= aoki_order:
                # そのカードは takahashi のもの
                right = mid
            else:
                left = mid
        return n - right

            

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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 = []
for s,t in zip_longest(T0,T1):
    T.append(s)
    T.append(t)
if T[-1] is None:
    T.pop()

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *
from bisect import *

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

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

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left

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

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


#t回でX以下のAsのみとなってしまうような最小のtを求める。
def calc_t(X):
    ok = -1
    ng = N+1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        aoki = mid // 2
        taka = mid - aoki
        aoki_max = As[-taka]
        aoki_min_index = bisect_left(As, 2*X - aoki_max)
        if N - taka - aoki_min_index < aoki:
            ng = mid
        else:
            ok = mid
    return ok

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

Submission status: Accepted

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]
    if n-(n-l)*2>0:ans+=+cs2[n-(n-l)*2]
    print(ans)

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

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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 = max(w1[-1],w2[-1])
    dic[x] = count
    print(count)
    return

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

Submission status: Accepted

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

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

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

su = sum(A)
# print(S,T)

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

Submission status: Accepted

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)
    return num+1 >= n - i

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

for j in range(q):
    x = int(input())
    l = 0
    r = n-1
    while l<r-1:
        m = (r+l)//2
        if sub(x, m):
            r = m
        else:
            l = m
    # rまではxより大きくて取れる
#     ans = sum(a[r:])
    ans = cumsum[-1] - cumsum[r-1]
    ii = r-2 - (n-r-1)
    if ii>=0:
        if ii%2:
            ans += cumsum1[ii]
        else:
            ans += cumsum0[ii]
    anss[j] = ans
write("\n".join(map(str, anss)))

Submission status: Accepted

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
cumsum = [0] * n
for i in range(n):
    if i%2:
        cumsum1[i] = cumsum1[i-1] + a[i]
        cumsum0[i] = cumsum0[i-1]
    else:
        cumsum0[i] = cumsum0[i-1] + a[i]
        cumsum1[i] = cumsum1[i-1]
    cumsum[i] = cumsum[i-1] + a[i]

for j in range(q):
    x = int(input())
    l = 0
    r = n-1
    while l<r-1:
        m = (r+l)//2
        if sub(x, m):
            r = m
        else:
            l = m
    # rまではxより大きくて取れる
#     ans = sum(a[r:])
    ans = cumsum[-1] - cumsum[r-1]
    ii = r-2 - (n-r-1)
    if ii>=0:
        if ii%2:
            ans += cumsum1[ii]
        else:
            ans += cumsum0[ii]
    anss[j] = ans
write("\n".join(map(str, anss)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *
from bisect import *

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

def binary_search():
    l, r = mark, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

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

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

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

def solve():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = [int(a) for a in input().split()]
    X = [int(input()) for _ in range(Q)]
    cont = [0] * N
    cont[N-1] = A[N-1]
    for i in reversed(range(N-1)): cont[i] = cont[i+1] + A[i]
    change = [0] * N
    change[0] = A[0]
    change[1] = A[1]
    for i in range(2, N): change[i] = change[i-2] + A[i]
    upperBound = [-1] * N
    for i in range((N + 1)// 2): #上からi+1個連続でとれるxの最大値
        target = A[N-i-1]
        lower = A[(N-i-1) - i]
        upperBound[N-i-1] = (target + lower) // 2
    upperBound[N-1] = 10 ** 10
    Ans = [0] * Q
    for i, x in enumerate(X):
        pos = bisect_left(upperBound, x)
        Ans[i] += cont[pos] #連続で取れる数
        if N - (N - pos) * 2 - 1 >= 0: Ans[i] += change[N - (N - pos) * 2 - 1]
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import bisect
import sys

input=sys.stdin.readline

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

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

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

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

Submission status: Accepted

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

for i in range(n):
    odd = i&1
    every2[odd][i//2 + 1] = every2[odd][i//2] + A[i]
    right[i+1] = right[i] + A[-i-1]
# 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: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import *

def judge(x):
    a = N-x
    b = x-bisect_left(A, X-(A[x]-X))+1
    
    return a<=b

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

N, Q = map(int, input().split())
A = list(map(int, input().split()))
acc = [0]*(N+1)
eacc = [0]*(N+1)

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

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