oj.uz

Submission #466479

# Submission time Handle Problem Language Result Execution time Memory
466479 2021-08-19T12:30:11 Z nathanlee726 Bitaro, who Leaps through Time (JOI19_timeleap) C++14
0 / 100
 748 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;
}
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
*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 0 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 1 ms 320 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 592 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 2 ms 588 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 2 ms 588 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 588 KB Output is correct
30 Correct 2 ms 516 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct
33 Correct 2 ms 588 KB Output is correct
34 Correct 2 ms 588 KB Output is correct
35 Correct 2 ms 588 KB Output is correct
36 Correct 3 ms 588 KB Output is correct
37 Correct 2 ms 588 KB Output is correct
38 Correct 2 ms 592 KB Output is correct
39 Correct 2 ms 588 KB Output is correct
40 Correct 2 ms 588 KB Output is correct
41 Runtime error 295 ms 524292 KB Execution killed with signal 9

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 748 ms 91344 KB Output is correct
2 Correct 708 ms 73032 KB Output is correct
3 Correct 681 ms 73092 KB Output is correct
4 Correct 713 ms 72876 KB Output is correct
5 Correct 660 ms 106448 KB Output is correct
6 Correct 653 ms 98884 KB Output is correct
7 Correct 688 ms 119932 KB Output is correct
8 Correct 671 ms 123784 KB Output is correct
9 Correct 614 ms 73072 KB Output is correct
10 Correct 662 ms 115448 KB Output is correct
11 Correct 688 ms 106500 KB Output is correct
12 Correct 731 ms 123648 KB Output is correct
13 Correct 673 ms 123872 KB Output is correct
14 Runtime error 275 ms 524292 KB Execution killed with signal 9

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 0 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 1 ms 320 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 592 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 2 ms 588 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 2 ms 588 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 588 KB Output is correct
30 Correct 2 ms 516 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct
33 Correct 2 ms 588 KB Output is correct
34 Correct 2 ms 588 KB Output is correct
35 Correct 2 ms 588 KB Output is correct
36 Correct 3 ms 588 KB Output is correct
37 Correct 2 ms 588 KB Output is correct
38 Correct 2 ms 592 KB Output is correct
39 Correct 2 ms 588 KB Output is correct
40 Correct 2 ms 588 KB Output is correct
41 Runtime error 295 ms 524292 KB Execution killed with signal 9