Submission #1256051

#TimeUsernameProblemLanguageResultExecution timeMemory
1256051trandangquangBitaro, who Leaps through Time (JOI19_timeleap)C++20
0 / 100
352 ms589824 KiB
#include<bits/stdc++.h> using namespace std; #define foru(i,a,b) for(int i=(a); i<=(b); ++i) #define ll long long const int N=300300; int n,q; int fl[N],fr[N]; struct Node{ int x,y; ll p=-1; void print(){ printf("x: %d, y: %d, p: %lld\n",x,y,p); } }; Node combine(Node u, Node v){ if(u.p==-1 && v.p==-1){ if(u.x>v.y) return Node{u.x, v.y, u.x-v.y}; if(u.y<v.x) return Node{u.y, v.x, 0}; return Node{max(u.x,v.x), min(u.y,v.y), -1}; } else if(u.p==-1 && v.p!=-1){ return Node{min(max(u.x,v.x),u.y), v.y, v.p+max(0,u.x-v.x)}; } else if(v.p==-1 && u.p!=-1){ return Node{u.x, max(min(u.y,v.y),v.x), u.p+max(0,u.y-v.y)}; } else{ return Node{u.x, v.y, u.p+v.p+max(0,u.y-v.x)}; } return Node{-1,-1,-1}; } struct SegmentTree{ int mode; Node st[N<<2]; void build(int id, int l, int r){ if(l==r){ if(mode==1) st[id]={fl[l]-l, fr[l]-l-1, -1}; else if(mode==2) st[id]={fl[l]-(n-l), fr[l]-(n-l)-1, -1}; return; } int mid=(l+r)>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); if(mode==1) st[id]=combine(st[id<<1],st[id<<1|1]); else st[id]=combine(st[id<<1|1],st[id<<1]); } void upd(int x, int s, int t){ int id=1, l=1, r=n-1; while(true){ if(l==r) break; int mid=(l+r)>>1; if(x<=mid){ id=id<<1; r=mid; } else{ id=id<<1|1; l=mid+1; } } st[id]={s,t,-1}; while(id>1){ id/=2; if(mode==1) st[id]=combine(st[id<<1],st[id<<1|1]); else st[id]=combine(st[id<<1|1],st[id<<1]); } } Node get(int u, int v, int id, int l, int r){ if(u<=l&&r<=v) return st[id]; int mid=(l+r)>>1; if(v<=mid) return get(u,v,id<<1,l,mid); if(u>mid) return get(u,v,id<<1|1,mid+1,r); if(mode==1) return combine(get(u,v,id<<1,l,mid), get(u,v,id<<1|1,mid+1,r)); else return combine(get(u,v,id<<1|1,mid+1,r), get(u,v,id<<1,l,mid)); } } st1, st2; int32_t main(){ // freopen("test.inp","r",stdin); // freopen("test.out","w",stdout); cin.tie(0)->sync_with_stdio(0); cin>>n>>q; foru(i,1,n-1){ cin>>fl[i]>>fr[i]; } st1.mode=1; st1.build(1,1,n-1); st2.mode=2; st2.build(1,1,n-1); foru(i,1,q){ int t; cin>>t; if(t==1){ int p,s,e; cin>>p>>s>>e; st1.upd(p,s-p,e-p-1); st2.upd(p,s-(n-p),e-(n-p)-1); } else{ int a,b,c,d; cin>>a>>b>>c>>d; if(a==c){ cout<<max(0,b-d)<<'\n'; continue; } Node tmp; if(a<c){ b-=a, d-=c; tmp=combine(combine(Node{b,b,-1},st1.get(a,c-1,1,1,n-1)),Node{d,d,-1}); } else{ b-=n-(a-1), d-=n-(c-1); tmp=combine(combine(Node{b,b,-1},st2.get(c,a-1,1,1,n-1)),Node{d,d,-1}); } cout<<max(0ll,tmp.p)<<'\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...