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: Runtime Error

Solution code:
from bisect import bisect_left
N,Q,*L = map(int, open(0).read().split())
A = L[:N]
S = []
M = []
x = 0
y = 0
m = sum(A)
for i in range(N):
  if i%2==0:
    x += A[i]
    S.append(x)
  else:
    y += A[i]
    S.append(y)
for i in range(N):
  M.append(m)
  m -= A[i]

for q in L[N:]:
  i = bisect_left(A,q)
  if 0<i and q-A[i-1]<=A[i]-q:
    i = i-1
  if i>=N-1:
    print(S[N-1])
    continue
  l = -1
  r = N
  while l+1<r:
    s = (l+r)//2
    k = N-1-s
    if s<=i:
      l = s
      continue
    x = s-i+1
    if x>k:
      r = s
      continue
    y = k-x
    m = i-y-1
    if m<0:
      l = s
      continue
    if q-A[m]<=A[s]-q:
      r = s
    else:
      l = s
  a = M[r]
  cnt = N-r
  cnt -= r-i-1
  b = i-cnt
  if b>=0:
    a += S[b]
  print(a)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
import bisect
n,q = map(int,input().split())
if n%2:
  a = [0]+list(map(int,input().split()))
  n += 1
else:
  a = list(map(int,input().split()))
fs = [a[i] if i%2 else 0 for i in range(n)]
accss = [0]*n
accff = list(accumulate(a))
accfs = list(accumulate(fs))
xls = []
xpt = []
for i in range(n//2):
  xls.append((a[2*i+1]+a[i+n//2])/2)
  if i == 0:
    xpt.append(accff[n-1]-accff[n//2-1])
  else:
    xpt.append(accff[n-1]-accff[i+n//2-1]+accfs[2*i-1])
for _ in range(q):
  x = bisect.bisect_left(xls,int(input()))
  if x >= n-1:
    print(xpt[-1])
  else:
    print(xpt[x])

Submission status: Runtime Error

Solution code:
from itertools import accumulate
import bisect
n,q = map(int,input().split())
if n%2:
  a = [0]+list(map(int,input().split()))
  n += 1
else:
  a = list(map(int,input().split()))
fs = [a[i] if i%2 else 0 for i in range(n)]
accss = [0]*n
accff = list(accumulate(a))
accfs = list(accumulate(fs))
xls = []
xpt = []
print(accff)
print(accfs)
for i in range(n//2):
  xls.append((a[2*i+1]+a[i+n//2])/2)
  if i == 0:
    xpt.append(accff[n-1]-accff[n//2-1])
  else:
    xpt.append(accff[n-1]-accff[i+n//2-1]+accfs[2*i-1])
for _ in range(q):
  x = bisect.bisect_left(xls,int(input()))
  if x >= n-1:
    print(xpt[-1])
  else:
    print(xpt[x])

Submission status: Runtime Error

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 + 1)
cs2 = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]
for i in range(N - 1, -1, -2): cs2[i + 1] = a[i]
for i in range(N): cs2[i + 1] += cs2[i]
res = [0] * (N + 1)
for i in range(N + 1):
  res[i] = cs[-1] - cs[min(N, i + N // 2)] + cs2[min(N, i * 2)]
#print(res, cs, cs2)
for _ in range(Q):
  x = int(input())
  i = bl(a, x)
  if abs(a[i - 1] - x) <= abs(a[i] - x): i -= 1
  y = max(0, i - N // 4)
  print(res[y])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d1 = []
d2 = []
for i in range(3):
  if a[i] < b[i]: d1.append((a[i], b[i]))
  if a[i] > b[i]: d2.append((b[i], a[i]))

dp = [0] * (N + 1)

for i in range(N, -1, -1):
  for t in d1:
    x = t[0]
    y = t[1]
    if i - x >= 0:
      dp[i - x] += y + dp[i]
for i in range(N + 1): dp[i] += i
res1 = max(dp)
#print(dp)
dp2 = [0] * (res1 + 1)
for i in range(res1, -1, -1):
  for t in d2:
    x = t[0]
    y = t[1]
    if i - x >= 0:
      dp2[i - x] += y
for i in range(res1 + 1): dp2[i] += i
print(max(dp2))

Submission status: Runtime Error

Solution code:
//header
#define set_header 1
#ifdef set_header
    #include <bits/stdc++.h>
    #ifdef LOCAL
        #include "cxx-prettyprint-master/prettyprint.hpp"
        #define print(x) cout << x << endl
    #else
        #define print(...) 42
    #endif
    using namespace std;
    using ll = long long;
    #define INF 1'010'000'000'000'000'017LL
    #define mod 998244353LL
    #define eps 0.0001
    #define all(x) (x).begin(), (x).end()
    #define reverse(x) (x).rbegin(), (x).rend()
    #define FOR(i,a,b) for(ll i=(a);i<(b);++i)
    #define rep(i,n)  FOR(i,0,n)
    #define SZ(x) ((ll)(x).size())
    #define sum(x) accumulate(ALL(x), 0LL)//?
    #define pb(x) push_back(x)
    typedef pair < ll , ll >P;
    ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
    template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
    template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
    template <std::uint_fast64_t Modulus> class modint {
        using u64 = std::uint_fast64_t;

        public:
        u64 a;

        constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
        constexpr u64 &value() noexcept { return a; }
        constexpr const u64 &value() const noexcept { return a; }
        constexpr modint operator+(const modint rhs) const noexcept {
            return modint(*this) += rhs;
        }
        constexpr modint operator-(const modint rhs) const noexcept {
            return modint(*this) -= rhs;
        }
        constexpr modint operator*(const modint rhs) const noexcept {
            return modint(*this) *= rhs;
        }
        constexpr modint operator/(const modint rhs) const noexcept {
            return modint(*this) /= rhs;
        }
        constexpr modint &operator+=(const modint rhs) noexcept {
            a += rhs.a;
            if (a >= Modulus) {
            a -= Modulus;
            }
            return *this;
        }
        constexpr modint &operator-=(const modint rhs) noexcept {
            if (a < rhs.a) {
            a += Modulus;
            }
            a -= rhs.a;
            return *this;
        }
        constexpr modint &operator*=(const modint rhs) noexcept {
            a = a * rhs.a % Modulus;
            return *this;
        }
        constexpr modint &operator/=(modint rhs) noexcept {
            u64 exp = Modulus - 2;
            while (exp) {
            if (exp % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
            }
            return *this;
        }
        };
    template< typename T >
    T mod_pow(T x, T n, const T &p) {
        T ret = 1;
        while(n > 0) {
            if(n & 1) (ret *= x) %= p;
            (x *= x) %= p;
            n >>= 1;
        }
        return ret;
    }
    class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
    public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};
    uint64_t my_rand(void) {
	static uint64_t x = 88172645463325252ULL;
	x = x ^ (x << 13); x = x ^ (x >> 7);
	return x = x ^ (x << 17);
}
#endif
//library
int N;
vector<ll> A;
bool C(ll x, ll y){
    int r = distance(begin(A), upper_bound(all(A), y));
    int l = distance(begin(A), lower_bound(all(A), x*2-y));
    if(N-r >= r-l) return true;
    return false;
}
//main
int main() {
    int Q;
    cin >> N >> Q;
    A.resize(N);
    vector<ll> S(N+1), S0(N+1), S1(N+1);
    rep(i, N){
        cin >> A[i];
        S[i+1] = S[i]+A[i];
        if(i%2 == 0){
            S0[i+1] = S0[i]+A[i];
            S1[i+1] = S1[i];
        }else{
            S1[i+1] = S1[i]+A[i];
            S0[i+1] = S0[i];
        }
    }
    rep(i, Q){
        ll x;
        cin >> x;
        ll ok = x, ng = A[N-1];
        while((ng-ok)>1){
            ll mid = (ok+ng)/2;
            if(C(x, mid))ok = mid;
            else ng = mid;
        }
        ll y = ok;
        int r = distance(begin(A), upper_bound(all(A), y));
        int l = distance(begin(A), upper_bound(all(A), x*2-y));
        if(N-r-(r-l) > 1)l--;
        ll taka = S[N]-S[r];
        if(N-r-(r-l) == l%2)taka+=S1[l];
        else taka+=S0[l];
        cout << taka << endl;
    }

}

Submission status: Runtime Error

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*q
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=nn

    for i,ini in ix:
        while check(k)==True:k-=1
        k+=1
        ans[i]=aac[-1]-aac[-k-1]+aac2[-k-1]
    for i in ans:
        print(i)
main()

Submission status: Runtime Error

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*n
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=nn-1

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

Submission status: Runtime Error

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*n
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=nn

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

Submission status: Runtime Error

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

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

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

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

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cfloat>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ll long long
#define eps LDBL_EPSILON
#define mod (int)1000000007
#define INF LLONG_MAX/10
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int gcd(int a, int b) {
	if (!b)return a;
	return gcd(b, a % b);
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}
bool isprime(int n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
int mypow(int a, int b) {
	if (!b)return 1;
	if (b % 2)return mypow(a, b - 1) * a;
	int memo = mypow(a, b / 2);
	return memo * memo;
}
int modpow(int a, int b, int m = mod) {
	if (!b)return 1;
	if (b % 2)return modpow(a, b - 1, m) * a % m;
	int memo = modpow(a, b / 2, m);
	return memo * memo % m;
}
class modInt {
	int value, modulo;
public:
	template<typename T>
	constexpr modInt(T value = 0, int modulo = mod) : value(value), modulo(modulo) { value %= T(modulo); }
	inline constexpr operator int()const { return value; }
	inline constexpr modInt& operator+=(modInt x) {
		value += x.value;
		if (value >= modulo)value -= modulo;
		return *this;
	}
	inline constexpr modInt& operator++() {
		if (value == modulo - 1)value = 0;
		else value++;
		return *this;
	}
	inline constexpr modInt& operator-()const {
		return modInt(0) -= *this;
	}
	inline constexpr modInt& operator-=(modInt x) {
		value -= x.value;
		if (value < 0)value += modulo;
		return *this;
	}
	inline constexpr modInt& operator--() {
		if (value == 0)value = modulo - 1;
		else value--;
		return *this;
	}
	inline constexpr modInt& operator*=(modInt x) {
		value = value * x.value % mod;
		return *this;
	}
	inline modInt& operator/=(modInt x) {
		return operator*=(x.inv());
	}
	modInt pow(modInt x, int y) {
		if (!y)return 1;
		if (y & 1)return pow(x, y - 1);
		modInt memo = pow(x, y / 2);
		return memo * memo;
	}
	inline modInt inv() {
		return pow(*this, modulo - 2);
	}
	template<typename T> modInt operator+(T x) { return modInt(*this) += x; }
	template<typename T> modInt& operator+=(T x) { return modInt(*this) += modInt(x); }
	template<typename T> modInt operator-(T x) { return modInt(*this) -= x; }
	template<typename T> modInt& operator-=(T x) { return modInt(*this) -= modInt(x); }
	template<typename T> modInt operator*(T x) { return modInt(*this) *= x; }
	template<typename T> modInt& operator*=(T x) { return modInt(*this) *= modInt(x); }
	template<typename T> modInt operator/(T x) { return modInt(*this) /= x; }
	template<typename T> modInt& operator/=(T x) { return modInt(*this) /= modInt(x); }
};
istream& operator>>(istream ist, modInt& x) {
	int a;
	ist >> a;
	x = a;
	return ist;
}
class UnionFind {
	int* par, * rank;
	P* notparent;
	vector<P>* size;
	int opcount = 0;
public:
	UnionFind(unsigned int size) {
		par = new int[size + 1];
		rank = new int[size + 1];
		this->size = new vector<P>[size + 1];
		notparent = new P[size + 1];
		rep(i, size + 1) {
			par[i] = i;
			rank[i] = 0;
			this->size[i].push_back(make_pair(-1, 1));
			notparent[i] = make_pair(INF, i);
		}
	}
	int find(int n, int t = INF) {
		if (opcount <= t) {
			if (par[n] == n)return n;
			return par[n] = find(par[n]);
		}
		if (notparent[n].first <= t)return find(notparent[n].second, t);
		return n;
	}
	void unite(int n, int m) {
		n = find(n);
		m = find(m);
		if (n == m) {
			opcount++;
			return;
		}
		if (rank[n] < rank[m]) {
			par[n] = m;
			notparent[n] = make_pair(opcount, m);
			size[m].push_back(make_pair(opcount, size[m].back().second + size[n].back().second));
		}
		else {
			par[m] = n;
			notparent[m] = make_pair(opcount, n);
			size[n].push_back(make_pair(opcount, size[n].back().second + size[m].back().second));
			if (rank[n] == rank[m])rank[n]++;
		}
		opcount++;
	}
	bool same(int n, int m, int t = INF) {
		return find(n, t) == find(m, t);
	}
	int getsize(int n, int t = INF) {
		n = find(n, t);
		auto ite = lower_bound(size[n].begin(), size[n].end(), make_pair(t, (int)0));
		if (ite == size[n].end())ite--;
		if (t < (*ite).first)ite--;
		return (*ite).second;
	}
};
class RollingHash {
	string s;
	int n, m, base;
	deque<int> has;
public:
	RollingHash(string s, int m, int b) : n(s.size()), m(m), base(b) { init(s, m, b); }
	void init(string s, int m, int b) {
		n = s.size();
		has.resize(n);
		base = b;
		this->s = s;
		this->m = m;
		rep(i, n) {
			has[i] = (int)s[i];
			if (i)has[i] += base * has[i - 1] % m;
			has[i] %= m;
		}
	}
	operator int() const {
		return has.back();
	}
	void cut(int a, int b) {
		assert(!(a >= b || a < 0 || n < b));
		rep(i, a)has.pop_front();
		rep(i, n - b)has.pop_back();
		s = s.substr(a, b);
		int memo = modpow(modpow(base, n - b, m), m - 2, m);
		rep(i, b - a) {
			has[i] *= memo;
			has[i] %= mod;
		}
		n = b - a;
	}
	int query(int a, int b) {
		assert(!(a >= b || a < 0 || n < b));
		return (has[b - 1] - modpow(base, b - a, m) * (!a ? 0 : has[a - 1]) % m + m) % m;
	}
	int operator+(RollingHash t) {
		assert(m == t.m && base == t.base);
		return (has[n - 1] * modpow(base, t.n, m) % m + t.has[t.n - 1]) % m;
	}
	RollingHash& operator+=(string t) {
		s += t;
		has.resize(n + t.size());
		for (int i = n; i < n + t.size(); i++) {
			has[i] = (int)t[i] * base % m;
			has[i] += base * has[i - 1] % m;
			has[i] %= m;
		}
		n += t.size();
		return *this;
	}
};
template<typename T, typename U>
class SegTree {
	int n = 1;
	T* node = NULL;
	U* lazy = NULL;
	bool* lazyflag = NULL;
	T nodee;
	U lazye;
	function<T(T, T)> nodef;
	function<U(U, U)> lazyf;
	function<T(int, T, U)> updf;
	void eval(int k, int l, int r) {
		if (lazyflag[k]) {
			node[k] = updf(r - l, node[k], lazy[k]);
			if (r - l > 1) {
				lazyflag[2 * k + 1] = lazyflag[2 * k + 2] = true;
				lazy[2 * k + 1] = lazyf(lazy[2 * k + 1], lazy[k]);
				lazy[2 * k + 2] = lazyf(lazy[2 * k + 2], lazy[k]);
			}
			lazyflag[k] = false;
			lazy[k] = lazye;
		}
	}
public:
	SegTree(int m, int init, T nodee, U lazye, function<T(T, T)> nodef, function<U(U, U)> lazyf, function<T(int, T, U)> updf) :nodee(nodee), lazye(lazye), nodef(nodef), lazyf(lazyf), updf(updf) {
		delete[] node;
		delete[] lazy;
		while (n < m)n *= 2;
		node = new T[2 * n], lazy = new U[2 * n], lazyflag = new bool[2 * n];
		rep(i, 2 * n) {
			node[i] = init;
			lazy[i] = lazye;
			lazyflag[i] = false;
		}
	}
	~SegTree() {
		delete[] node;
		delete[] lazy;
	}
	void update(int a, int b, U x, int k = 0, int l = 0, int r = -1) {
		if (r == -1)r = n;
		eval(k, l, r);
		if (b <= l || r <= a)return;
		if (a <= l && r <= b) {
			lazyflag[k] = true;
			lazy[k] = x;
			eval(k, l, r);
		}
		else {
			update(a, b, x, 2 * k + 1, l, (l + r) / 2);
			update(a, b, x, 2 * k + 2, (l + r) / 2, r);
			node[k] = nodef(node[2 * k + 1], node[2 * k + 2]);
		}
	}
	T query(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r == -1)r = n;
		eval(k, l, r);
		if (b <= l || r <= a)return nodee;
		if (a <= l && r <= b)return node[k];
		T vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
		T vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
		return nodef(vl, vr);
	}
};
class Matrix {
	int n;
	vector<vector<int>> vec;
	void Measure() {
		rep(i, n) {
			rep(j, n) {
				if (i != j)vec[i][j] = 0;
				else vec[i][j] = 1;
			}
		}
	}
public:
	Matrix(int n) {
		this->n = n;
		vec.resize(n, vector<int>(n));
	}
	Matrix(int n, vector<int> vec) {
		if (vec.size() != n * n) {
			cerr << "Invalid construct of matrix" << endl;
			exit(1);
		}
		this->n = n;
		this->vec.resize(n, vector<int>(n));
		rep(i, n) {
			rep(j, n)this->vec[i][j] = vec[i * n + j];
		}
	}
	int operator[](int a) {
		return vec[a / n][a % n];
	}
	unsigned int size() { return n; }
	Matrix operator*(const Matrix a) {
		if (this->n != a.n) {
			cerr << "Invalid maltiply of matrix" << endl;
			exit(1);
		}
		vector<int> memo(n);
		rep(i, n) {
			rep(j, n) {
				rep(k, n) {
					memo[j] += vec[i][k] * a.vec[k][j];
				}
			}
			vec[i] = memo;
			memo.clear();
			memo.resize(n);
		}
		return *this;
	}
	Matrix letmod(int m = mod) {
		rep(i, n) {
			rep(j, n)vec[i][j] %= m;
		}
		return *this;
	}
	static Matrix measure(int n) {
		Matrix res(n);
		res.Measure();
		return res;
	}
	static Matrix mypow(Matrix a, int b, int m = mod) {
		a.letmod(m);
		if (!b)return Matrix::measure(a.size());
		if (b % 2)return (mypow(a, b - 1, m) * a).letmod(m);
		Matrix memo = mypow(a, b / 2, m);
		return (memo * memo).letmod(m);
	}
};
class mycomplex {
	double realvalue, imagvalue;
public:
	mycomplex() :realvalue(0), imagvalue(0) {}
	mycomplex(double realvalue, double imagvalue) : realvalue(realvalue), imagvalue(imagvalue) {}
	mycomplex(double realvalue) : realvalue(realvalue), imagvalue(0) {}
	mycomplex(complex<double> c) :realvalue(c.real()), imagvalue(c.imag()) {}
	mycomplex(const mycomplex& rhs) :realvalue(rhs.realvalue), imagvalue(rhs.imagvalue) {}
	double real()const { return this->realvalue; }
	double imag()const { return this->imagvalue; }
	double abs() { return hypot(realvalue, imagvalue); }
	mycomplex& operator=(const mycomplex& obj) {
		if (this != &obj) {
			this->realvalue = obj.realvalue;
			this->imagvalue = obj.imagvalue;
		}
		return *this;
	}
	mycomplex& operator=(mycomplex&& obj)noexcept {
		if (this != &obj) {
			this->realvalue = exchange(obj.realvalue, 0);
			this->imagvalue = exchange(obj.imagvalue, 0);
		}
		return *this;
	}
	mycomplex& operator+=(const mycomplex& rhs) {
		this->realvalue += rhs.realvalue;
		this->imagvalue += rhs.imagvalue;
		return *this;
	}
	friend mycomplex operator+(mycomplex lhs, const mycomplex& rhs) {
		lhs += rhs;
		return lhs;
	}
	mycomplex& operator-=(const mycomplex& rhs) {
		this->realvalue -= rhs.realvalue;
		this->imagvalue -= rhs.imagvalue;
		return *this;
	}
	mycomplex& operator-=(const double& rhs) {
		this->realvalue -= rhs;
		return *this;
	}
	friend mycomplex operator-(mycomplex lhs, const mycomplex& rhs) {
		lhs -= rhs;
		return lhs;
	}
	mycomplex& operator*=(const mycomplex& rhs) {
		double pastreal = this->realvalue;
		this->realvalue = this->realvalue * rhs.realvalue - this->imagvalue * rhs.imagvalue;
		this->imagvalue = pastreal * rhs.imagvalue + rhs.realvalue * this->imagvalue;
		return *this;
	}
	friend mycomplex operator*(mycomplex lhs, const mycomplex& rhs) {
		lhs *= rhs;
		return lhs;
	}
	mycomplex& operator/=(const mycomplex& rhs) {
		*this *= mycomplex(rhs.real(), -rhs.imag());
		double dnm = rhs.real() * rhs.real() - rhs.imag() * rhs.imag();
		this->realvalue /= dnm;
		this->imagvalue /= dnm;
		return *this;
	}
	friend mycomplex operator/(mycomplex lhs, const mycomplex& rhs) {
		lhs /= rhs;
		return lhs;
	}
};
class FastFourierTransform {
private:
	static void dft(vector<mycomplex>& func, int inverse) {
		int sz = func.size();
		if (sz == 1)return;
		vector<mycomplex> veca, vecb;
		rep(i, sz / 2) {
			veca.push_back(func[2 * i]);
			vecb.push_back(func[2 * i + 1]);
		}
		dft(veca, inverse); dft(vecb, inverse);
		mycomplex now = 1, zeta = polar(1.0, inverse * 2.0 * acos(-1) / sz);
		rep(i, sz) {
			func[i] = veca[i % (sz / 2)] + now * vecb[i % (sz / 2)];
			now *= zeta;
		}
	}
public:
	template<typename T>
	static vector<double> multiply(vector<T> f, vector<T> g) {
		vector<mycomplex> nf, ng;
		int sz = 1;
		while (sz < f.size() + g.size())sz *= 2;
		nf.resize(sz); ng.resize(sz);
		rep(i, f.size()) {
			nf[i] = f[i];
			ng[i] = g[i];
		}
		dft(nf, 1);
		dft(ng, 1);
		rep(i, sz)nf[i] *= ng[i];
		dft(nf, -1);
		vector<double> res;
		rep(i, sz)res.push_back(nf[i].real() / sz);
		return res;
	}
};
int n, q, a[100010], b[100010], c[100010], x;
signed main() {
	cin >> n >> q;
	rep(i, n) {
		cin >> a[i];
		c[i] = b[i] = a[i];
	}
	for (int i = 2; i < n; i++)b[i] += b[i - 2];
	for (int i = n - 2; i >= 0; i--)c[i] += c[i + 1];
	rep(i, q) {
		cin >> x;
		int ok = -2, ng = 1000000000;
		while (ok + 1 < ng) {
			int md = (ok + ng) / 2;
			int l = lower_bound(a, a + n, x - md) - a, r = upper_bound(a, a + n, x + md) - a;
			if (r - l <= n - r)ok = md;
			else ng = md;
		}
		int l = lower_bound(a, a + n, x - ok) - a, r = upper_bound(a, a + n, x + ok) - a;
		int nl = lower_bound(a, a + n, x - ng) - a, nr = upper_bound(a, a + n, x + ng) - a;
		if (r - l + 1 < nr - nl && r - l + 1 <= n - r)l--;
		if ((n - l) % 2 == 0 && l)cout << c[r] + b[l - 1] << endl;
		else if ((n - l) % 2 && l >= 2)cout << c[r] + b[l - 2] << endl;
		else cout << c[r] << endl;
	}
	return 0;
}

Submission status: Runtime Error

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

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

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

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

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

import sys
input = sys.stdin.readline

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

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

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

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

Submission status: Runtime Error

Solution code:

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 = (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: Runtime Error

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())
    small_id = bisect.bisect_left(a, x) - 1
    big_id = small_id + 1
    if x - a[small_id] <= a[big_id] - x:
        l = small_id
    else:
        l = big_id
    r = n
    l -= 1
    while r - l > 1:
        mid = (l + r) // 2
        t_turn = n - mid
        a_lower_value = x - (a[mid] - x)
        a_turn = mid - bisect.bisect_left(a, a_lower_value) + 1
        if a_turn >= t_turn:
            r = mid
        else:
            l = mid
    ll = bisect.bisect_left(a, x - (a[l] - x))
    if ll > l:
        ll = l
    if n -1 - l <= l+1 - ll:
        takahashi = cuma[n] - cuma[l+1] + bipartite_cuma[ll+1]
        aoki = cuma[l+1] - cuma[ll] + bipartite_cuma[ll]
    else:
        takahashi = cuma[n] - cuma[l+1] + bipartite_cuma[ll]
        aoki = cuma[l+1] - cuma[ll] + bipartite_cuma[ll+1]
    print(takahashi)

Submission status: Runtime Error

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

card = sorted(a_list)

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

Submission status: Runtime Error

Solution code:
import bisect

 
n, q = map(int, input().split())
a_list = list(map(int, input().split()))
xnum = [0]*q
for i in range(q):
    xnum[i] = int(input())
 
card = sorted(a_list)
 
for x in xnum:
    xpos = bisect.bisect(card, x)
    cnt = 0
    upos = 1
    lpos = 1
    for i in range(n):
        if abs(card[xpos+upos] - x) < abs(card[xpos-lpos] - x):
            upos += 1
        else:
            lpos += 1
        if i+1 + upos >= n-xpos:
            break
    i += 1
    print(sum(card[-i:]) + (sum(card[:n-2*i][::-2]) if 2*i < n else 0))