Submission #1275614

#TimeUsernameProblemLanguageResultExecution timeMemory
1275614ayxanesedzade10Monkey and Apple-trees (IZhO12_apple)C++20
0 / 100
1 ms572 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const ll sz=2e5+100;
const ll MAX=1e9+7;
ll st[sz*40][3],lazy[sz*40];
ll last=1;
void push(ll l,ll r,ll ind){
if(lazy[ind]==0) return;
st[ind][2]=r-l+1;
if(l!=r){
    lazy[st[ind][0]]=1;
    lazy[st[ind][1]]=1;
}
lazy[ind]=0;
}
void update(ll l,ll r,ll a,ll b,ll ind){
    push(l,r,ind);
    if(l>b or r<a) return;
    if(!st[ind][0]){
        st[ind][0]=++last;st[ind][1]=++last;
    }
    if(l>=a and r<=b){
        lazy[ind]=1;
        push(l,r,ind);
        return;
    }
    ll mid=(l+r)/2;
    update(l,mid,a,b,st[ind][0]);
    update(mid+1,r,a,b,st[ind][1]);
    st[ind][2]=st[st[ind][0]][2]+st[st[ind][1]][2];
}
ll ask(ll l,ll r,ll a,ll b,ll ind){
    if(!st[ind][0]){
        st[ind][0]=++last;
        st[ind][1]=++last;
    }
    push(l,r,ind);
    if(ind==0) return 0;
    if(l>b or r<a) return 0;
    if(l>=a and r<=b) return st[ind][2];
    ll mid=(l+r)/2;
    return ask(l,mid,a,b,st[ind][0])+ask(mid+1,r,a,b,st[ind][1]);
}
int main(){
    ll m,c=0;cin>>m;
    for(int i=1;i<=m;i++){
        ll d,x,y;cin>>d>>x>>y;
        if(d==2){
            x=x+c;y=y+c;
            update(1,MAX,x,y,1);
        }
        else{
            x=x+c;y=y+c;
            ll res=ask(1,MAX,x,y,1);
            cout<<res<<endl;c=res;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...