Submission #1275912

#TimeUsernameProblemLanguageResultExecution timeMemory
1275912ayxanesedzade10Monkey and Apple-trees (IZhO12_apple)C++20
0 / 100
526 ms265924 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=1e5+100;
ll st[160*sz][4],last=1;
void push(ll l,ll r,ll ind)
{
    if(!st[ind][1]){
        st[ind][1]=++last;
        st[ind][2]=++last;
    }
    if(st[ind][3]==0) return;
    st[ind][0]=r-l+1;
    if(l!=r){
        st[st[ind][1]][3]=1;st[st[ind][2]][3]=1;
    }
    st[ind][3]=0;
}
void update(ll l,ll r,ll a,ll b,ll ind)
{
    if(!st[ind][1]){
        st[ind][1]=++last;
        st[ind][2]=++last;
    }
    push(l,r,ind);
    if(l>b or r<a) return;
    if(l>=a and r<=b){
        st[ind][3]=1;push(l,r,ind);return;
    }
    ll mid=(l+r)/2;
    update(l,mid,a,b,st[ind][1]);
    update(mid+1,r,a,b,st[ind][2]);
    st[ind][0]=st[st[ind][1]][0]+st[st[ind][2]][0];
}
ll ask(ll l,ll r,ll a,ll b,ll ind)
{
    push(l,r,ind);
    if(l>b or r<a) return 0;
    if(l>=a and r<=b) return st[ind][0];
    ll mid=(l+r)/2;
    return ask(l,mid,a,b,st[ind][1])+ask(mid+1,r,a,b,st[ind][2]);
}
int main()
{
    ll m,n=1e9+100,c=0;cin>>m;
    for(int i=1;i<=m;i++){
        ll d,x,y;cin>>d>>x>>y;
        if(d==1){
            x=x+c;y=y+c;
            ll res=ask(1,n,x,y,1);
            cout<<res<<endl;c=res;
        }
        else{
            x=x+c;y=y+c;
            update(1,n,x,y,1);
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...