# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1000925 | ayankarimova | Monkey and Apple-trees (IZhO12_apple) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll sz=*6e6+6;
const ll mod=1e9+7;
ll st[sz], le[sz], re[sz], nxt=1, lazy[sz];
void relax(ll l, ll r, ll in)
{
if(lazy[in]){
st[in]=r-l+1;
if(l!=r){
if(!le[in]) le[in]=++nxt;
if(!re[in]) re[in]=++nxt;
lazy[le[in]]=1;
lazy[re[in]]=1;
}
lazy[in]=0;
}
}
void update(ll l, ll r, ll in, ll ql, ll qr)
{
relax(l, r, in);
if(ql>r || qr<l) return;
if(ql<=l && r<=qr){
st[in]=r-l+1;
if(l!=r){
if(!le[in]) le[in]=++nxt;
if(!re[in]) re[in]=++nxt;
lazy[le[in]]=1;
lazy[re[in]]=1;
}
return;
}
ll mid=(l+r)/2;
if(!le[in]) le[in]=++nxt;
update(l, mid, le[in], ql, qr);
if(!re[in]) re[in]=++nxt;
update(mid+1, r, re[in], ql, qr);
st[in]=st[le[in]]+st[re[in]];
}
ll res(ll l, ll r, ll in, ll ql, ll qr)
{
relax(l, r, in);
if(ql>r || qr<l) return 0;
if(ql<=l && r<=qr) return st[in];
ll mid=(l+r)/2;
ll q1, q2;
if(le[in]) q1=res(l, mid, le[in], ql, qr);
else q1=0;
if(re[in]) q2=res(mid+1, r, re[in], ql, qr);
else q2=0;
return q1+q2;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll m;
cin>>m;
ll c=0;
while(m--){
ll t, a, b;
cin>>t>>a>>b;
if(t==2){
a+=c; b+=c;
update(1, 1e9, 1, a, b);
}
else{
a+=c; b+=c;
ll ans=res(1, 1e9, 1, a, b);
cout<<ans<<endl;
c=ans;
}
}
}
/*
{}[]
*/