提出 #3996155

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

int N, Q, A[100001];
int64_t S[100001], Sdiv[100001];
int X[100000];
int64_t ans[100000];

int main(){
    cin >> N >> Q;
    for(int i=1; i<=N; i++){
        cin >> A[i];
        S[i] = S[i-1] + A[i];
        Sdiv[i] = A[i];
        if(i-2 > 0) Sdiv[i] += Sdiv[i-2];
    }
    for(int i=0; i<Q; i++) cin >> X[i];

    for(int q=0; q<Q; q++){
        int ng = 0;
        int ok = N;
        while(ok-ng>1){
            int mid = (ng+ok)/2;
            if(A[mid] < X[q]){
                ng = mid;
            }else{
                int upper = N - mid + 1;
                int lower = mid - (lower_bound(A, A+N+1, max(1, 2*X[q]-A[mid])) - A) + 1;
                (upper > lower ? ng : ok) = mid;
            }
        }

        int64_t result = S[N] - S[ok-1];
        int t_first = N - (N-ok+1)*2;
        if(t_first > 0) result += Sdiv[t_first];
        ans[q] = result;
    }
    for(int i=0; i<Q; i++) cout << ans[i] << endl;
    return 0;
}

提出情報

ジャッジ結果