Submission #3988902


Source Code Expand

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

int N, Q, A[100001];
int64_t S[100001], Sdiv[100001];
pair<int, 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++){
        int x;
        cin >> x;
        X[i] = {x, i};
    }
    sort(X, X+Q);

    int y = 1;
    for(int q=0; q<Q; q++){
        int x = X[q].first;
        while(y<=N && A[y] < x) y++;
        while(y<=N){
            int upper = N - y + 1;
            int lower = y - (lower_bound(A, A+N+1, max(1, 2*x-A[y])) - A) + 1;
            if(upper > lower){
                y++;
            }else{
                break;
            }
        }
        int64_t result = S[N] - S[y-1];
        int t_first = N - (N-y+1)*2;
        if(t_first > 0) result += Sdiv[t_first];
        ans[X[q].second] = result;
    }
    for(int i=0; i<Q; i++) cout << ans[i] << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Nearest Card Game
User betrue12
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1078 Byte
Status
Exec Time 277 ms
Memory 5248 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt
All 500 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01.txt 7 ms 384 KB
02.txt 7 ms 384 KB
03.txt 7 ms 384 KB
04.txt 7 ms 384 KB
05.txt 7 ms 384 KB
06.txt 5 ms 256 KB
07.txt 212 ms 2816 KB
08.txt 274 ms 5248 KB
09.txt 228 ms 3072 KB
10.txt 216 ms 3072 KB
11.txt 275 ms 5248 KB
12.txt 274 ms 5248 KB
13.txt 267 ms 5248 KB
14.txt 270 ms 5248 KB
15.txt 267 ms 5248 KB
16.txt 268 ms 5248 KB
17.txt 273 ms 5248 KB
18.txt 272 ms 5248 KB
19.txt 270 ms 5248 KB
20.txt 246 ms 4864 KB
21.txt 246 ms 4864 KB
22.txt 272 ms 5248 KB
23.txt 277 ms 5248 KB
24.txt 275 ms 5248 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB