提出 #3988902


ソースコード 拡げる

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;
}

提出情報

提出日時
問題 D - Nearest Card Game
ユーザ betrue12
言語 C++14 (GCC 5.4.1)
得点 500
コード長 1078 Byte
結果
実行時間 277 ms
メモリ 5248 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
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
ケース名 結果 実行時間 メモリ
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