Submission #1000952

#TimeUsernameProblemLanguageResultExecution timeMemory
1000952ayankarimovaMonkey and Apple-trees (IZhO12_apple)C++14
100 / 100
211 ms133712 KiB
#include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll int const ll sz=(2e5+5)*30; const int long n=1e9; ll st[sz*4], le[sz*4], re[sz*4], nxt=1, lazy[sz*4]; 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, n, 1, a, b); } else{ a+=c; b+=c; ll ans=res(1, n, 1, a, b); cout<<ans<<endl; c=ans; } } } /* {}[] */
#Verdict Execution timeMemoryGrader output
Fetching results...