Submission #708776

#TimeUsernameProblemLanguageResultExecution timeMemory
708776alvingogoBitaro, who Leaps through Time (JOI19_timeleap)C++14
0 / 100
446 ms123980 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define AquA cin.tie(0);ios_base::sync_with_stdio(0); #define fs first #define sc second #define p_q priority_queue #define int long long using namespace std; const int inf=1e9; vector<pair<int,int> > gg[2]; struct ST{ int tp; struct no{ int ax,ay,bx; // <=ax : ay // >=bx : by=bx+(ay-ax) int dx,dy; // <=dx : dy // >=dx : linear }; vector<no> st; pair<int,int> get(no& a,int x){ pair<int,int> ret; if(x<=a.ax){ ret.fs=a.ay; } else if(x>=a.bx){ ret.fs=a.bx+a.ay-a.ax; } else{ ret.fs=a.ay+(x-a.ax); } if(x<=a.dx){ ret.sc=a.dy; } else{ ret.sc=a.dy+x-a.dx; } return ret; } void upd(int v,int l,int r){ st[v].ax=l; st[v].ay=l+1; st[v].bx=r; st[v].dx=r; st[v].dy=0; } void pull(int v){ auto p=st[2*v+1],q=st[2*v+2]; if(get(q,p.ay).fs==get(q,p.bx+p.ay-p.ax).fs){ st[v].ax=st[v].bx=0; st[v].ay=get(q,p.ay).fs; } else{ st[v].ax=p.ax+max(0ll,q.ax-p.ay); st[v].ay=get(q,get(p,st[v].ax).fs).fs; st[v].bx=p.bx-max(0ll,p.bx+p.ay-p.ax-q.bx); } int c=get(p,0).sc+get(q,get(p,0).fs).sc,d=get(p,inf).sc+get(q,get(p,inf).fs).sc; st[v].dx=inf-(d-c); st[v].dy=c; } void build(int v,int L,int R){ if(L==R){ upd(v,gg[tp][L].fs,gg[tp][L].sc); return; } int m=(L+R)/2; build(2*v+1,L,m); build(2*v+2,m+1,R); pull(v); } void print(int v){ cout << v << ":" << "\n"; cout << st[v].ax << " " << st[v].ay << " " << st[v].bx << "\n"; cout << st[v].dx << " " << st[v].dy << "\n\n"; } void init(int x){ st.resize(4*x); build(0,0,x-1); } void update(int v,int L,int R,int p,int l,int r){ if(L==R){ upd(v,l,r); return; } int m=(L+R)/2; if(p<=m){ update(2*v+1,L,m,p,l,r); } else{ update(2*v+2,m+1,R,p,l,r); } pull(v); } pair<int,int> query(int v,int L,int R,int l,int r,int x){ if(L==l && R==r){ return get(st[v],x); } int m=(L+R)/2; if(r<=m){ return query(2*v+1,L,m,l,r,x); } else if(l>m){ return query(2*v+2,m+1,R,l,r,x); } else{ auto h=query(2*v+1,L,m,l,m,x); auto y=query(2*v+2,m+1,R,m+1,r,h.fs); return {y.fs,y.sc+h.sc}; } } }st[2]; signed main(){ AquA; int n,q; cin >> n >> q; n--; gg[0].resize(n); gg[1].resize(n); for(int i=0;i<n;i++){ cin >> gg[0][i].fs >> gg[0][i].sc; gg[0][i].sc--; } gg[1]=gg[0]; reverse(gg[1].begin(),gg[1].end()); st[0].tp=0; st[1].tp=1; st[0].init(n); st[1].init(n); for(int i=0;i<4*n;i++){ //st[1].print(i); } //cout << st.st[0].ax << " " << st.st[0].ay << " " << st.st[0].bx << " " << st.st[0].dx << " " << st.st[0].dy << '\n'; //cout << st.get(st.st[0],3).fs << " " << st.get(st.st[0],3).sc << "\n"; for(int i=0;i<q;i++){ int t; cin >> t; if(t==1){ int a,l,r; cin >> a >> l >> r; a--; r--; st[0].update(0,0,n-1,a,l,r); st[1].update(0,0,n-1,n-a-1,l,r); } else{ int a,b,c,d; cin >> a >> b >> c >> d; if(a==c){ cout << max(0ll,b-d) << "\n"; continue; } if(a<c){ a--; c--; c--; auto h=st[0].query(0,0,n-1,a,c,b); cout << h.sc+(max(0ll,h.fs-d)) << "\n"; } else{ a--; c--; a=n-a; c=n-c; c--; //cout << a << " " << c << endl; auto h=st[1].query(0,0,n-1,a,c,b); cout << h.sc+(max(0ll,h.fs-d)) << "\n"; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...