oj.uz

Submission #466492

# Submission time Handle Problem Language Result Execution time Memory
466492 2021-08-19T12:55:33 Z nathanlee726 Bitaro, who Leaps through Time (JOI19_timeleap) C++14
0 / 100
 679 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;
	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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 584 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 512 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 584 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 460 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 588 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 2 ms 588 KB Output is correct
37 Correct 2 ms 588 KB Output is correct
38 Correct 2 ms 584 KB Output is correct
39 Correct 3 ms 588 KB Output is correct
40 Correct 2 ms 584 KB Output is correct
41 Runtime error 272 ms 524292 KB Execution killed with signal 9

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 91564 KB Output is correct
2 Correct 623 ms 58108 KB Output is correct
3 Correct 623 ms 58308 KB Output is correct
4 Correct 620 ms 58072 KB Output is correct
5 Correct 637 ms 91304 KB Output is correct
6 Correct 637 ms 83868 KB Output is correct
7 Correct 669 ms 104980 KB Output is correct
8 Correct 653 ms 107972 KB Output is correct
9 Correct 627 ms 58208 KB Output is correct
10 Correct 659 ms 100276 KB Output is correct
11 Correct 634 ms 91460 KB Output is correct
12 Correct 679 ms 108132 KB Output is correct
13 Correct 663 ms 108024 KB Output is correct
14 Runtime error 262 ms 524292 KB Execution killed with signal 9

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 584 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 512 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 584 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 460 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 588 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 2 ms 588 KB Output is correct
37 Correct 2 ms 588 KB Output is correct
38 Correct 2 ms 584 KB Output is correct
39 Correct 3 ms 588 KB Output is correct
40 Correct 2 ms 584 KB Output is correct
41 Runtime error 272 ms 524292 KB Execution killed with signal 9