Submission #466492

#TimeUsernameProblemLanguageResultExecution timeMemory
466492nathanlee726Bitaro, who Leaps through Time (JOI19_timeleap)C++14
0 / 100
679 ms524292 KiB
//#include<i_am_noob_orz> #include<bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define ll long long #define int ll #define ull unsigned long long #define pii pair<int,int> #define X first #define Y second #define mod ((ll)1e9+7) #define pb push_back #define mp make_pair #define abs(x) ((x)>0?(x):(-(x))) #define F(n) Fi(i,n) #define Fi(i,n) Fl(i,0,n) #define Fl(i,l,n) for(int i=l;i<n;i++) #define memres(a) memset(a,0,sizeof(a)) #define all(a) a.begin(),a.end() #define sz(a) ((int)a.size()) #define ceiling(a,b) (((a)+(b)-1)/(b)) #define endl '\n' #define bit_count(x) __builtin_popcountll((x)) #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define jimmy_is_kind false typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree; //#define LOCAL #ifdef LOCAL #define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__) template<typename T> void _do(T && x) {cerr<<x<<endl;} template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);} #define IOS() #else #define IOS() ios_base::sync_with_stdio(0), cin.tie(0) #define endl '\n' #define bug(...) #endif int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);} int sub(int a,int b){return(a<b?a+mod-b:a-b);} int po(int a,int b){ if(b==0)return 1; if(b==1)return(a%mod); int tem=po(a,b/2); if(b&1)return(((tem*tem)%mod)*a)%mod; else return(tem*tem)%mod; } int GCD(int a,int b){ int x=0; int ra,rb; while(a&&b){ if(((a&1)==0)&&((b&1)==0)){ a>>=1,b>>=1,x++; } else if((a^b)&1){ if(a&1)b>>=1; else a>>=1; } else{ ra=abs(a-b),rb=min(a,b); a=ra,b=rb; } } return max(a,b)<<x; } int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);} int n,q; pii ar[300010]; struct NODE{ int bl,br,tl,tr,vl,vr; }seg[1200010][2]; pii get_new(int al,int ar,int bl,int br){ if(bl>=ar){ return{ar-1,ar}; } else if(br<=al){ return{al,al+1}; } else {bug(al,ar,bl,br);return{max(al,bl),min(ar,br)};} } void pull(int p,int l,int mi,int r){ pii npi=get_new(seg[p*2][0].bl,seg[p*2][0].br,seg[p*2+1][0].bl-(mi+1-l),seg[p*2+1][0].br-(mi+1-l)); pii npi1,npi2={0,0}; if(npi.X>seg[p*2][0].bl)npi1.X=npi.X+(mi+1-l); else npi1.X=seg[p*2][0].tl,npi2.X+=(seg[p*2][0].vl); if(npi.Y<seg[p*2][0].br)npi1.Y=npi.Y+(mi+1-l); else npi1.Y=seg[p*2][0].tr,npi2.Y+=seg[p*2][0].vr; if(npi1.X<=seg[p*2+1][0].bl)npi1.X=seg[p*2+1][0].tl,npi2.X+=seg[p*2+1][0].vl; else if(npi1.X>=seg[p*2+1][0].br)npi2.X+=(npi1.X-seg[p*2+1][0].br+seg[p*2+1][0].vr),npi1.X=seg[p*2+1][0].tr; else npi1.X+=(r-mi); if(npi1.Y<=seg[p*2+1][0].bl)npi1.Y=seg[p*2+1][0].tl,npi2.Y+=seg[p*2+1][0].vl; else if(npi1.Y>=seg[p*2+1][0].br)npi2.Y+=(npi1.Y-seg[p*2+1][0].br+seg[p*2+1][0].vr),npi1.Y=seg[p*2+1][0].tr; else npi1.Y+=(r-mi); seg[p][0].bl=npi.X,seg[p][0].br=npi.Y; seg[p][0].tl=npi1.X,seg[p][0].tr=npi1.Y; seg[p][0].vl=npi2.X,seg[p][0].vr=npi2.Y; // npi=get_new(seg[p*2+1][1].bl,seg[p*2+1][1].br,seg[p*2][1].bl-(r-mi),seg[p*2][1].br-(r-mi)); npi2={0,0}; if(npi.X>seg[p*2+1][1].bl)npi1.X=npi.X+(r-mi); else npi1.X=seg[p*2+1][1].tl,npi2.X+=(seg[p*2+1][1].vl); if(npi.Y<seg[p*2+1][1].br)npi1.Y=npi.Y+(r-mi); else npi1.Y=seg[p*2+1][1].tr,npi2.Y+=seg[p*2+1][1].vr; if(npi1.X<=seg[p*2][1].bl)npi1.X=seg[p*2][1].tl,npi2.X+=seg[p*2][1].vl; else if(npi1.X>=seg[p*2][1].br)npi2.X+=(npi1.X-seg[p*2][1].br+seg[p*2][1].vr),npi1.X=seg[p*2][1].tr; else npi1.X+=(mi+1-l); if(npi1.Y<=seg[p*2][1].bl)npi1.Y=seg[p*2][1].tl,npi2.Y+=seg[p*2][1].vl; else if(npi1.Y>=seg[p*2][1].br)npi2.Y+=(npi1.Y-seg[p*2][1].br+seg[p*2][1].vr),npi1.Y=seg[p*2][1].tr; else npi1.Y+=(mi+1-l); seg[p][1].bl=npi.X,seg[p][1].br=npi.Y; seg[p][1].tl=npi1.X,seg[p][1].tr=npi1.Y; seg[p][1].vl=npi2.X,seg[p][1].vr=npi2.Y; assert(seg[p][0].bl>=-1&&seg[p][1].bl>=-1); } void build(int p,int l,int r){ if(l==r){ seg[p][0].bl=seg[p][1].bl=ar[l].X-1; seg[p][0].br=seg[p][1].br=ar[l].Y+1; seg[p][0].tl=seg[p][1].tl=ar[l].X+1; seg[p][0].tr=seg[p][1].tr=ar[l].Y+1; seg[p][0].vl=seg[p][1].vl=0; seg[p][0].vr=seg[p][1].vr=1; return; } int mi=(l+r)/2; build(p*2,l,mi); build(p*2+1,mi+1,r); pull(p,l,mi,r); } void modify(int p,int l,int r,int x){ if(l==r){ seg[p][0].bl=seg[p][1].bl=ar[l].X-1; seg[p][0].br=seg[p][1].br=ar[l].Y+1; seg[p][0].tl=seg[p][1].tl=ar[l].X+1; seg[p][0].tr=seg[p][1].tr=ar[l].Y+1; return; } int mi=(l+r)/2; if(mi>=x)modify(p*2,l,mi,x); else modify(p*2+1,mi+1,r,x); pull(p,l,mi,r); } pii query(int p,int l,int r,int ql,int qr,int x,int ty){ if(l>=ql&&r<=qr){ if(ty==0){ int tp,tv=0; if(x<=seg[p][0].bl)tp=seg[p][0].tl,tv+=seg[p][0].vl; else if(x>=seg[p][0].br)tv+=(x-seg[p][0].br+seg[p][0].vr),tp=seg[p][0].tr; else tp=x+(r+1-l); return{tp,tv}; } else{ int tp,tv=0; if(x<=seg[p][1].bl)tp=seg[p][1].tl,tv+=seg[p][1].vl; else if(x>=seg[p][1].br)tv+=(x-seg[p][1].br+seg[p][1].vr),tp=seg[p][1].tr; else tp=x+(r+1-l); return{tp,tv}; } } int mi=(l+r)/2; if(ty==0){ int nx=x,tv=0; if(mi>=ql){ pii tpi=query(p*2,l,mi,ql,qr,nx,ty); tv+=tpi.Y; nx=tpi.X; } if(mi+1<=qr){ pii tpi=query(p*2+1,mi+1,r,ql,qr,nx,ty); tv+=tpi.Y; nx=tpi.X; } bug(l,r,nx,tv); return{nx,tv}; } else{ int nx=x,tv=0; if(mi+1<=qr){ pii tpi=query(p*2+1,mi+1,r,ql,qr,nx,ty); tv+=tpi.Y; nx=tpi.X; } if(mi>=ql){ pii tpi=query(p*2,l,mi,ql,qr,nx,ty); tv+=tpi.Y; nx=tpi.X; } bug(l,r,nx,tv); return{nx,tv}; } } signed main(){ IOS(); cin>>n>>q; F(n-1)cin>>ar[i].X>>ar[i].Y,ar[i].Y--; build(1,0,n-2); bug(seg[1][0].bl,seg[1][0].br); F(q){ int ty; cin>>ty; if(ty==1){ int x,y,z; cin>>x>>y>>z; --x,--z; ar[x]={y,z}; modify(1,0,n-2,x); } else{ int x,y,z,w; cin>>x>>y>>z>>w; --x,--z; if(x==z){ cout<<max(0ll,y-w)<<endl; continue; } if(x<z){ pii tpi=query(1,0,n-2,x,z-1,y,0); //bug(tpi.X,tpi.Y); if(w<tpi.X)tpi.Y+=(tpi.X-w); cout<<tpi.Y<<endl; } else{ pii tpi=query(1,0,n-2,z,x-1,y,1); //bug(tpi.X,tpi.Y); if(w<tpi.X)tpi.Y+=(tpi.X-w); cout<<tpi.Y<<endl; } } } return 0; } /* 4 1 0 1 999999998 999999999 0 1 2 1 999999999 4 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...