D - Home Garden セグ木で殴る

解説

code

#include <atcoder/lazysegtree>
using namespace atcoder; // 忘れがち

// 区間加算・区間和取得
struct S{
    long long value;
    int size;
};
using F = long long;

S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {x.value + f*x.size, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    std::vector<S> v(200000+10, {0, 1});
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);

    // input
    ll Q;cin>>Q;
    ll plant_cnt=0;
    ll current_pos=0;
    while(Q--){
      ll ty;cin>>ty;

      if(ty==1){
        // うえる
        plant_cnt++;
      }
      else if(ty==2){
        // T日まつ
        ll T;cin>>T;
        seg.apply(0, plant_cnt, T); // 足す
      }
      else{
        // 収穫
        ll H;cin>>H;
        ll harvest_cnt=0;
        while(true){
          ll h = seg.prod(current_pos, current_pos+1).value;
          if(h>=H){
            harvest_cnt++;
            current_pos++;
          }else{
            break;
          }
        }
        p(harvest_cnt);
      }
    }

    return 0;
}