제출 #1063789

#제출 시각아이디문제언어결과실행 시간메모리
1063789Drifter24Monkey and Apple-trees (IZhO12_apple)C++17
100 / 100
362 ms207804 KiB
#include <bits/stdc++.h> using namespace std; typedef long long T; T null=0, noVal=0; T oper(T a, T b){return a+b;} struct Node{ T val,lz; int l,r; Node *pl,*pr; Node(int ll, int rr){ val=null;lz=noVal; pl=pr=nullptr; l=ll;r=rr; } }; typedef Node* PNode; void update(PNode x){ if(x->r-x->l==1)return; x->val=oper(x->pl->val, x->pr->val); } void extends(PNode x){ if(x->r-x->l!=1 && !x->pl){ int m=(x->r+x->l)/2; x->pl=new Node(x->l, m); x->pr=new Node(m, x->r); } } void propagate(PNode x){ if(x->r-x->l==1)return; if(x->lz==noVal)return; int m=(x->r+x->l)/2; x->pl->lz=1; x->pl->val=m-x->l; x->pr->lz=1; x->pr->val=x->r-m; x->lz=noVal; } struct SegTree{ PNode root; void upd(PNode x, int l, int r, T v){ int lx=x->l,rx=x->r; if(lx>=r || l>=rx)return; if(lx>=l && rx<=r){ x->lz=1; x->val=rx-lx; return; } extends(x); propagate(x); upd(x->pl,l,r,v); upd(x->pr,l,r,v); update(x); } T get(PNode x, int l, int r){ int lx=x->l,rx=x->r; if(lx>=r || l>=rx)return null; if(lx>=l && rx<=r)return x->val; extends(x); propagate(x); T v1=get(x->pl,l,r); T v2=get(x->pr,l,r); return oper(v1,v2); } void upd(int l, int r, T v){upd(root,l,r+1,v);} T get(int l, int r){return get(root,l,r+1);} void build(int l, int r){root=new Node(l, r+1);} }; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int q; cin>>q; T ans=0,op,l,r; SegTree st; st.build(1,1e9); while(q--){ cin>>op>>l>>r; l+=ans; r+=ans; if(op==1ll){ ans=st.get(l,r); cout<<ans<<"\n"; }else{ st.upd(l,r,1ll); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...