Submission #3624430

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

const ll max_b = 200002;
ll bit[max_b];

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

void add(ll i, ll x){
  while(i<=max_b){
    bit[i]+=x;
    i+=i&-i;
  }
}

pair<ll,ll> search(ll x, bool lower_bound){
  ll lb = 0, ub = max_b, mid;
  while(ub-lb>1){
    mid = (ub+lb)/2;
    if(sum(mid)<x) lb = mid;
    else if(sum(mid)>x) ub = mid;
    else if(lower_bound) ub = mid;
    else lb = mid;
  }
  return pair<ll,ll>(lb,ub);
}

int main(){
  ll n,m,h;
  cin >> n >> m >> h;
  REP(i,n){
    ll a; cin >> a;
    add(i+1,a);
  }
  ll index = n+1;
  REP(_,m){
    str opr; ll arg;
    cin >> opr >> arg;
    if(opr=="add"){
      add(index,arg);
      index++;
    }else{
      ll left = search(arg-h,false).second;
      ll right = search(arg+h,true).second;
      //printf("%ld %ld\n",left,right);
      if(left==right&&right!=max_b){
        cout << "go" << endl;
        add(left,-sum(left)+sum(left-1));
      }else if(right==max_b){
        cout << "miss" << endl;
      }else{
        cout << "stop" << endl;
      }
    }
  }
  return 0;
}

Submission Info

Judge Result