oj.uz

Submission #466494

# Submission time Handle Problem Language Result Execution time Memory
466494 2021-08-19T12:57:43 Z nathanlee726 Bitaro, who Leaps through Time (JOI19_timeleap) C++14
100 / 100
 785 ms 120684 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;
			}
		}
	}
	return 0;
	}
	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
4.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 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 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 3 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 3 ms 540 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 3 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 484 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 3 ms 460 KB Output is correct
40 Correct 2 ms 460 KB Output is correct
41 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 90924 KB Output is correct
2 Correct 631 ms 57744 KB Output is correct
3 Correct 631 ms 57788 KB Output is correct
4 Correct 631 ms 57648 KB Output is correct
5 Correct 785 ms 90908 KB Output is correct
6 Correct 654 ms 83332 KB Output is correct
7 Correct 647 ms 104568 KB Output is correct
8 Correct 660 ms 107588 KB Output is correct
9 Correct 703 ms 57912 KB Output is correct
10 Correct 692 ms 99812 KB Output is correct
11 Correct 636 ms 90932 KB Output is correct
12 Correct 662 ms 107580 KB Output is correct
13 Correct 664 ms 107628 KB Output is correct
14 Correct 1 ms 204 KB Output is correct

Subtask #3
66.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 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 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 3 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 3 ms 540 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 3 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 484 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 3 ms 460 KB Output is correct
40 Correct 2 ms 460 KB Output is correct
41 Correct 1 ms 204 KB Output is correct
42 Correct 628 ms 90924 KB Output is correct
43 Correct 631 ms 57744 KB Output is correct
44 Correct 631 ms 57788 KB Output is correct
45 Correct 631 ms 57648 KB Output is correct
46 Correct 785 ms 90908 KB Output is correct
47 Correct 654 ms 83332 KB Output is correct
48 Correct 647 ms 104568 KB Output is correct
49 Correct 660 ms 107588 KB Output is correct
50 Correct 703 ms 57912 KB Output is correct
51 Correct 692 ms 99812 KB Output is correct
52 Correct 636 ms 90932 KB Output is correct
53 Correct 662 ms 107580 KB Output is correct
54 Correct 664 ms 107628 KB Output is correct
55 Correct 1 ms 204 KB Output is correct
56 Correct 632 ms 103248 KB Output is correct
57 Correct 663 ms 69748 KB Output is correct
58 Correct 626 ms 119984 KB Output is correct
59 Correct 641 ms 120040 KB Output is correct
60 Correct 607 ms 70048 KB Output is correct
61 Correct 702 ms 120404 KB Output is correct
62 Correct 662 ms 120224 KB Output is correct
63 Correct 634 ms 120216 KB Output is correct
64 Correct 657 ms 120404 KB Output is correct
65 Correct 752 ms 104800 KB Output is correct
66 Correct 645 ms 113536 KB Output is correct
67 Correct 636 ms 120232 KB Output is correct
68 Correct 598 ms 79480 KB Output is correct
69 Correct 742 ms 120520 KB Output is correct
70 Correct 635 ms 70012 KB Output is correct
71 Correct 656 ms 69188 KB Output is correct
72 Correct 605 ms 75212 KB Output is correct
73 Correct 672 ms 119904 KB Output is correct
74 Correct 650 ms 120012 KB Output is correct
75 Correct 738 ms 120148 KB Output is correct
76 Correct 673 ms 120684 KB Output is correct
77 Correct 1 ms 332 KB Output is correct