oj.uz

Submission #466493

# Submission time Handle Problem Language Result Execution time Memory
466493 2021-08-19T12:57:04 Z nathanlee726 Bitaro, who Leaps through Time (JOI19_timeleap) C++14
0 / 100
 705 ms 524292 KB 
//#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;
	if(n==1){
		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;
			}
		}
	}
	}
	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
*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 2 ms 460 KB Output is correct
35 Correct 2 ms 460 KB Output is correct
36 Correct 2 ms 460 KB Output is correct
37 Correct 2 ms 460 KB Output is correct
38 Correct 2 ms 460 KB Output is correct
39 Correct 2 ms 460 KB Output is correct
40 Correct 2 ms 460 KB Output is correct
41 Runtime error 256 ms 524292 KB Execution killed with signal 9

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 90960 KB Output is correct
2 Correct 631 ms 57792 KB Output is correct
3 Correct 603 ms 57852 KB Output is correct
4 Correct 626 ms 57636 KB Output is correct
5 Correct 631 ms 90856 KB Output is correct
6 Correct 703 ms 83484 KB Output is correct
7 Correct 653 ms 104512 KB Output is correct
8 Correct 705 ms 107608 KB Output is correct
9 Correct 627 ms 57960 KB Output is correct
10 Correct 655 ms 99740 KB Output is correct
11 Correct 633 ms 90956 KB Output is correct
12 Correct 655 ms 107588 KB Output is correct
13 Correct 664 ms 107844 KB Output is correct
14 Runtime error 260 ms 524292 KB Execution killed with signal 9

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 2 ms 460 KB Output is correct
35 Correct 2 ms 460 KB Output is correct
36 Correct 2 ms 460 KB Output is correct
37 Correct 2 ms 460 KB Output is correct
38 Correct 2 ms 460 KB Output is correct
39 Correct 2 ms 460 KB Output is correct
40 Correct 2 ms 460 KB Output is correct
41 Runtime error 256 ms 524292 KB Execution killed with signal 9