Submission #3889762


Source Code Expand

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)

using namespace std;
typedef long long int ll;
const int MAX_N=1e6;
ll bit[MAX_N+1];
int n,m,h;
ll sum(int i){
    ll s=0;
    while(i>0){
        s+=bit[i];
        i-=i&-i;
    }
    return s;
}

void add(int i, int x){
    while(i<=MAX_N){
        bit[i]+=x;
        i+=i&-i;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>h;
    rep(i,0,n){
        int A;
        cin>>A;
        add(i+1,A);
    }
    int end=n;
    rep(i,0,m){
        string s;
        ll a;
        cin>>s>>a;
        if(s=="add"){
            end++;
            add(end,a);
        }
        else{
            if(sum(end)<a-h) cout<<"miss"<<"\n";
            else{
                int lb1=0,ub1=1e5*3;
                while(ub1-lb1>1){
                    int mid1=(lb1+ub1)/2;
                    if(sum(mid1)>=a-h+1) ub1=mid1;
                    else lb1=mid1;
                }
                int lb2=0,ub2=1e5*3;
                while(ub2-lb2>1){
                    int mid2=(lb2+ub2)/2;
                    if(sum(mid2)>=a+h) ub2=mid2;
                    else lb2=mid2;
                }
                if(ub1==ub2||ub1==end){
                    cout<<"go"<<"\n";
                    add(ub1,-(sum(ub1)-sum(ub1-1)));
                }
                else{
                    cout<<"stop"<<"\n";
                }
            }
        }
    }
}

Submission Info

Submission Time
Task G - だるま落とし
User yuki1997
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1584 Byte
Status WA
Exec Time 91 ms
Memory 5888 KB

Judge Result

Set Name small large
Score / Max Score 0 / 20 0 / 80
Status
AC × 17
WA × 19
AC × 31
WA × 35
Set Name Test Cases
small small/case_000.txt, small/case_002.txt, small/case_003.txt, small/case_005.txt, small/case_006.txt, small/case_007.txt, small/case_008.txt, small/case_009.txt, small/case_010.txt, small/case_011.txt, small/case_012.txt, small/case_013.txt, small/case_014.txt, small/case_015.txt, small/case_016.txt, small/case_017.txt, small/case_018.txt, small/case_019.txt, small/case_020.txt, small/case_021.txt, small/case_022.txt, small/case_023.txt, small/case_024.txt, small/case_025.txt, small/case_026.txt, small/case_027.txt, small/case_028.txt, small/case_029.txt, small/case_030.txt, small/case_031.txt, small/case_032.txt, small/case_033.txt, small/case_034.txt, small/case_035.txt, small/case_036.txt, small/case_037.txt
large large/case_000.txt, large/case_002.txt, large/case_003.txt, large/case_005.txt, large/case_006.txt, large/case_007.txt, large/case_008.txt, large/case_009.txt, large/case_010.txt, large/case_011.txt, large/case_012.txt, large/case_013.txt, large/case_014.txt, large/case_015.txt, large/case_016.txt, large/case_017.txt, large/case_018.txt, large/case_019.txt, large/case_020.txt, large/case_021.txt, large/case_022.txt, large/case_023.txt, large/case_024.txt, large/case_025.txt, large/case_026.txt, large/case_027.txt, large/case_028.txt, large/case_029.txt, large/case_030.txt, large/case_031.txt, large/case_032.txt, large/case_033.txt, large/case_034.txt, large/case_035.txt, large/case_036.txt, large/case_037.txt, large/large_case_000.txt, large/large_case_001.txt, large/large_case_002.txt, large/large_case_003.txt, large/large_case_004.txt, large/large_case_005.txt, large/large_case_006.txt, large/large_case_007.txt, large/large_case_008.txt, large/large_case_009.txt, large/large_case_010.txt, large/large_case_011.txt, large/large_case_012.txt, large/large_case_013.txt, large/large_case_014.txt, large/large_case_015.txt, large/large_case_016.txt, large/large_case_017.txt, large/large_case_018.txt, large/large_case_019.txt, large/large_case_020.txt, large/large_case_021.txt, large/large_case_022.txt, large/large_case_023.txt, large/large_case_024.txt, large/large_case_025.txt, large/large_case_026.txt, large/large_case_027.txt, large/large_case_028.txt, large/large_case_029.txt
Case Name Status Exec Time Memory
large/case_000.txt AC 2 ms 4352 KB
large/case_002.txt AC 2 ms 4352 KB
large/case_003.txt WA 2 ms 4352 KB
large/case_005.txt AC 2 ms 4352 KB
large/case_006.txt WA 2 ms 4352 KB
large/case_007.txt WA 2 ms 4352 KB
large/case_008.txt AC 3 ms 4352 KB
large/case_009.txt AC 3 ms 4352 KB
large/case_010.txt AC 3 ms 4352 KB
large/case_011.txt AC 3 ms 4352 KB
large/case_012.txt AC 3 ms 4352 KB
large/case_013.txt AC 3 ms 4352 KB
large/case_014.txt AC 3 ms 4480 KB
large/case_015.txt AC 3 ms 4352 KB
large/case_016.txt AC 3 ms 4352 KB
large/case_017.txt AC 3 ms 4352 KB
large/case_018.txt AC 3 ms 4352 KB
large/case_019.txt AC 3 ms 4352 KB
large/case_020.txt AC 3 ms 4352 KB
large/case_021.txt AC 3 ms 4352 KB
large/case_022.txt WA 3 ms 4352 KB
large/case_023.txt WA 3 ms 4352 KB
large/case_024.txt WA 3 ms 4352 KB
large/case_025.txt WA 3 ms 4352 KB
large/case_026.txt WA 3 ms 4352 KB
large/case_027.txt WA 3 ms 4352 KB
large/case_028.txt WA 3 ms 4352 KB
large/case_029.txt WA 3 ms 4352 KB
large/case_030.txt WA 3 ms 4352 KB
large/case_031.txt WA 3 ms 4352 KB
large/case_032.txt WA 3 ms 4352 KB
large/case_033.txt WA 3 ms 4352 KB
large/case_034.txt WA 3 ms 4352 KB
large/case_035.txt WA 3 ms 4352 KB
large/case_036.txt WA 3 ms 4352 KB
large/case_037.txt WA 3 ms 4352 KB
large/large_case_000.txt AC 87 ms 5760 KB
large/large_case_001.txt AC 88 ms 5760 KB
large/large_case_002.txt AC 85 ms 5760 KB
large/large_case_003.txt AC 85 ms 5760 KB
large/large_case_004.txt AC 88 ms 5760 KB
large/large_case_005.txt AC 85 ms 5760 KB
large/large_case_006.txt AC 84 ms 5760 KB
large/large_case_007.txt AC 86 ms 5760 KB
large/large_case_008.txt AC 85 ms 5760 KB
large/large_case_009.txt AC 85 ms 5760 KB
large/large_case_010.txt AC 45 ms 5888 KB
large/large_case_011.txt AC 74 ms 5760 KB
large/large_case_012.txt AC 73 ms 5760 KB
large/large_case_013.txt AC 80 ms 5760 KB
large/large_case_014.txt WA 88 ms 5632 KB
large/large_case_015.txt WA 88 ms 5632 KB
large/large_case_016.txt WA 88 ms 5632 KB
large/large_case_017.txt WA 90 ms 5632 KB
large/large_case_018.txt WA 90 ms 5632 KB
large/large_case_019.txt WA 91 ms 5632 KB
large/large_case_020.txt WA 90 ms 5632 KB
large/large_case_021.txt WA 88 ms 5632 KB
large/large_case_022.txt WA 91 ms 5632 KB
large/large_case_023.txt WA 88 ms 5632 KB
large/large_case_024.txt WA 88 ms 5632 KB
large/large_case_025.txt WA 88 ms 5632 KB
large/large_case_026.txt WA 88 ms 5632 KB
large/large_case_027.txt WA 88 ms 5632 KB
large/large_case_028.txt WA 88 ms 5632 KB
large/large_case_029.txt WA 87 ms 5632 KB
small/case_000.txt AC 2 ms 4352 KB
small/case_002.txt AC 2 ms 4352 KB
small/case_003.txt WA 2 ms 4352 KB
small/case_005.txt AC 2 ms 4352 KB
small/case_006.txt WA 2 ms 4352 KB
small/case_007.txt WA 2 ms 4352 KB
small/case_008.txt AC 3 ms 4352 KB
small/case_009.txt AC 3 ms 4352 KB
small/case_010.txt AC 3 ms 4352 KB
small/case_011.txt AC 3 ms 4352 KB
small/case_012.txt AC 3 ms 4352 KB
small/case_013.txt AC 3 ms 4352 KB
small/case_014.txt AC 3 ms 4352 KB
small/case_015.txt AC 3 ms 4352 KB
small/case_016.txt AC 3 ms 4352 KB
small/case_017.txt AC 3 ms 4352 KB
small/case_018.txt AC 3 ms 4352 KB
small/case_019.txt AC 3 ms 4352 KB
small/case_020.txt AC 3 ms 4352 KB
small/case_021.txt AC 3 ms 4352 KB
small/case_022.txt WA 3 ms 4352 KB
small/case_023.txt WA 3 ms 4352 KB
small/case_024.txt WA 3 ms 4352 KB
small/case_025.txt WA 3 ms 4352 KB
small/case_026.txt WA 3 ms 4352 KB
small/case_027.txt WA 3 ms 4352 KB
small/case_028.txt WA 3 ms 4352 KB
small/case_029.txt WA 3 ms 4352 KB
small/case_030.txt WA 3 ms 4352 KB
small/case_031.txt WA 3 ms 4352 KB
small/case_032.txt WA 3 ms 4352 KB
small/case_033.txt WA 3 ms 4352 KB
small/case_034.txt WA 3 ms 4352 KB
small/case_035.txt WA 3 ms 4352 KB
small/case_036.txt WA 3 ms 4352 KB
small/case_037.txt WA 3 ms 4352 KB