Submission #1553349

---

Source Code Expand

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

const int MAX_N = 200000;

//[1, n]
vector<long long> bit(MAX_N + 1, 0);

int sum(int i){
    long long s = 0;
    while(i > 0){
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, long long x){
    while(i <= MAX_N){
        bit[i] += x;
        //bit[i] = max(bit[i], x);
        i += i & - i;
    }
}

int main(){
    int n, m;
    long long h;
    cin >> n >> m >> h;

    int block = n;
    rep(i,n){
        long long a;
        cin >> a;
        add(i + 1, a);
    }

    rep(j,m){
        string s;
        long long x;
        cin >> s >> x;
        if(s[0] == 'c'){
            int right = block + 5, left = 0;
            while(right - left > 1){
                int mid = (right + left) / 2;
                if(sum(mid) <= x - h) left = mid;
                else right = mid;
            }

            if(left == block + 5 - 1){
                cout << "miss" << endl;
                continue;
            }
            long long seg = sum(left + 1);
            long long total = sum(block + 5);
            if(seg != total && seg < x + h){
                cout << "stop" << endl;
            }else{
                cout << "go" << endl;
                add(left + 1, -bit[left + 1]);
            }
        }else{
            block++;
            add(block, x);
        }
    }
}

Submission Info

Judge Result