Submission #1184825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184825		Luvidi	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	285 ms	205736 KiB

apple

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

struct nd{
    int l,r,vl,lz,sz;
    nd *cl,*cr;
    nd(int L,int R){
        l=L;
        r=R;
        sz=r-l+1;
        cl=cr=NULL;
    }
    void pr(){
        if(lz){
            cl->lz=1;
            cl->vl=cl->sz;
            cr->lz=1;
            cr->vl=cr->sz;
        }
    }
    void upd(int l2,int r2){
        if(l2>r||r2<l)return;
        if(l2<=l&&r<=r2){
            lz=1;
            vl=sz;
        }else{
            int m=(l+r)/2;
            if(!cl)cl=new nd(l,m);
            if(!cr)cr=new nd(m+1,r);
            pr();
            cl->upd(l2,r2);
            cr->upd(l2,r2);
            vl=cl->vl+cr->vl;
        }
    }
    int qry(int l2,int r2){
        if(l2>r||r2<l)return 0;
        if(l2<=l&&r<=r2)return vl;
        int m=(l+r)/2;
        if(!cl)cl=new nd(l,m);
        if(!cr)cr=new nd(m+1,r);
        pr();
        return cl->qry(l2,r2)+cr->qry(l2,r2);
    }
    
};

void solve() {
    int n;
    cin>>n;
    nd *rt=new nd(0,1e9);
    int c=0;
    while(n--){
        int t,x,y;
        cin>>t>>x>>y;
        if(t==1){
            c=rt->qry(x+c,y+c);
            cout<<c<<'\n';
        }else{
            rt->upd(x+c,y+c);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
}

• Subtask 1: 100 / 100