제출 #1212828

#제출 시각아이디문제언어결과실행 시간메모리
1212828WarinchaiMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
236 ms124252 KiB
#include<bits/stdc++.h>
using namespace std;
struct node{
    int sum,lz;
    node *l,*r;
    node(int val=0){
        sum=val;
        lz=0;
        l=r=NULL;
    }
};
typedef node* pnode;
struct segtree{
    pnode rt=NULL;
    void push(int st,int en,pnode &x){
        if(x->lz){
            if(!x->l)x->l=new node();
            if(!x->r)x->r=new node();
            x->sum=en-st+1;
            x->l->lz=1;
            x->r->lz=1;
            x->lz=0;
        }
    }
    void upd(int st,int en,pnode &x,int l,int r){
        if(!x)x=new node();
        push(st,en,x);
        if(st>r||en<l)return;
        if(st>=l&&en<=r)return x->lz=1,push(st,en,x);
        int m=(st+en)/2;
        upd(st,m,x->l,l,r);
        upd(m+1,en,x->r,l,r);
        x->sum=x->l->sum+x->r->sum;
    }
    int fans(int st,int en,pnode x,int l,int r){
        if(!x)return 0;
        push(st,en,x);
        if(st>r||en<l)return 0;
        if(st>=l&&en<=r)return x->sum;
        int m=(st+en)/2;
        return fans(st,m,x->l,l,r)+fans(m+1,en,x->r,l,r);
    }
}tr;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m;cin>>m;
    int c=0;
    for(int i=0;i<m;i++){
        int t;cin>>t;
        int x,y;cin>>x>>y;
        x+=c,y+=c;
        if(t==1){
            int ans=tr.fans(1,1e7,tr.rt,x,y);
            cout<<ans<<"\n";
            c=ans;
        }else{
            tr.upd(1,1e7,tr.rt,x,y);
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...