제출 #647651

#제출 시각아이디문제언어결과실행 시간메모리
647651FerThugGato12500원숭이와 사과 나무 (IZhO12_apple)C++17
0 / 100
1 ms212 KiB
#include<bits/stdc++.h>
using namespace std;
const int lmt = 1e7 + 5;
struct Nodo{
    Nodo *ls, *rs;
    int v;
    Nodo(){
        ls = rs = NULL;
        v = 0;
    }
};
void insert(Nodo *tmp, int l, int r, int ini=0, int fin=lmt){
    if(ini>r || fin<l) return;
    if(ini>=l && fin<=r){ 
      
      tmp->v=(fin-ini)+1; 
      return; 
    }
    if(tmp->ls==NULL){
        if(tmp->v != 0){
          return;
        }
        tmp->ls = new Nodo();
        tmp->rs = new Nodo();
    }
    int mit = (ini+fin)/2;
    insert(tmp->ls, l, r, ini, mit);
    insert(tmp->rs, l, r, mit+1, fin);
  tmp->v = tmp->ls->v + tmp->rs->v;
    return;
}
int query(Nodo *tmp, int l, int r, int ini = 0, int fin=lmt){
    if(ini>r || fin<l){
        return 0;
    }
    if(ini>=l && fin<=r) return tmp->v;
    int mit = (ini+fin)/2;
    if(tmp->ls==NULL){
        tmp->ls = new Nodo();
        tmp->rs = new Nodo();
        if(tmp->v != 0){
          tmp->ls->v = (mit-ini)+1;
          tmp->rs->v = (fin-(mit+1))+1;
        }
    }
    int a = query(tmp->ls, l, r, ini, mit) + query(tmp->rs, l, r, mit+1, fin);

  tmp->v = tmp->ls->v + tmp->rs->v;
  return a;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int q; cin>>q;
    long long c=0;
    Nodo *root = new Nodo();
    while(q--){
        int z,x,y; cin>>z>>x>>y;
        x+=c; y+=c;
        if(z==2){
            insert(root, x, y);
        }else{
            int r = query(root, x, y);
            cout<<r<<"\n";
            c += r;
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...