Submission #164358

#	Time	Username	Problem	Language	Result	Execution time	Memory
164358		HungAnhGoldIBO2020	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	942 ms	142908 KiB

timeleap

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+2;
struct node{
	int l,r,real_l,real_r,pts,cost=0;
	node operator+(node other){
		node ans;
		ans.cost = cost + other.cost;
		ans.real_l = max(real_l, other.real_l);
		ans.real_r = min(real_r, other.real_r);
		if(ans.real_l <= ans.real_r){
			ans.pts = ans.real_r;
			ans.cost = 0;
			ans.l = ans.real_l;
			ans.r = ans.real_r;
		}
		else{
			if(real_l <= real_r){
				if(other.real_l <= other.real_r){
					if(other.l > r){
						ans.l = ans.r = other.l;
						ans.cost += 0;
						ans.pts = real_r;
					}
					else{
						ans.l = ans.r = other.r;
						ans.cost += l - other.r;
						ans.pts = l;
					}
				}
				else{
					ans.l = other.l;
					ans.r = other.r;
					if(other.pts > r){
						ans.cost += 0;
						ans.pts = r;
					}
					else{
						if(other.pts >= l){
							ans.cost += 0;
							ans.pts = other.pts;
						}
						else{
							ans.cost += l - other.pts;
							ans.pts = l;
						}
					}
				}
			}
			else{
				if(l > other.pts){
					ans.cost += l - other.pts;
				}
				ans.pts = pts;
				if(other.r < l){
                    ans.l = ans.r = other.r;
                }
                else{
					if(other.l <= l){
	                    ans.l = ans.r = l;
	                }
	                else{
	                    ans.l = ans.r = other.l;
	                }
	            }
			}
		}
		return ans;
	}
};
node it[4*N],it_rev[4*N];
pair<int,int> lis[N],lis_rev[N];
void build(int idx,int l,int r){
	if(l==r){
		it[idx].l = it[idx].real_l = lis[l].first;
		it[idx].r = it[idx].real_r = lis[l].second;
		it[idx].pts = it[idx].real_r;
		it[idx].cost = 0;
		return;
	}
	build(2*idx,l,(l+r)/2);
	build(2*idx+1,(l+r)/2+1,r);
	it[idx]=it[2*idx]+it[2*idx+1];
}
void upd(int idx,int l,int r,int pos,pair<int,int> val){
	if(l>pos||r<pos){
		return;
	}
	if(l==r){
		it[idx].l = it[idx].real_l = val.first;
		it[idx].r = it[idx].real_r = val.second;
		it[idx].pts = it[idx].real_r;
		it[idx].cost = 0;
		return;
	}
	upd(2*idx,l,(l+r)/2,pos,val);
	upd(2*idx+1,(l+r)/2+1,r,pos,val);
	it[idx]=it[2*idx]+it[2*idx+1];
}
node get(int idx,int l,int r,int lef,int rig){
	if(l>=lef&&r<=rig){
		return it[idx];
	}
	int mid=(l+r)/2;
	if(lef>mid){
		return get(2*idx+1,mid+1,r,lef,rig);
	}
	if(mid>=rig){
		return get(2*idx,l,mid,lef,rig);
	}
	return get(2*idx,l,mid,lef,rig)+get(2*idx+1,mid+1,r,lef,rig);
}
void build_rev(int idx,int l,int r){
	if(l==r){
		it_rev[idx].l = it_rev[idx].real_l = lis_rev[l].first;
		it_rev[idx].r = it_rev[idx].real_r = lis_rev[l].second;
		it_rev[idx].pts = it_rev[idx].real_r;
		it_rev[idx].cost = 0;
		return;
	}
	build_rev(2*idx,l,(l+r)/2);
	build_rev(2*idx+1,(l+r)/2+1,r);
	it_rev[idx]=it_rev[2*idx]+it_rev[2*idx+1];
}
void upd_rev(int idx,int l,int r,int pos,pair<int,int> val){
	if(l>pos||r<pos){
		return;
	}
	if(l==r){
		it_rev[idx].l = it_rev[idx].real_l = val.first;
		it_rev[idx].r = it_rev[idx].real_r = val.second;
		it_rev[idx].pts = val.second;
		it_rev[idx].cost = 0;
		return;
	}
	upd_rev(2*idx,l,(l+r)/2,pos,val);
	upd_rev(2*idx+1,(l+r)/2+1,r,pos,val);
	it_rev[idx]=it_rev[2*idx]+it_rev[2*idx+1];
}
node get_rev(int idx,int l,int r,int lef,int rig){
	if(l>=lef&&r<=rig){
		return it_rev[idx];
	}
	int mid=(l+r)/2;
	if(lef>mid){
		return get_rev(2*idx+1,mid+1,r,lef,rig);
	}
	if(mid>=rig){
		return get_rev(2*idx,l,mid,lef,rig);
	}
	return get_rev(2*idx,l,mid,lef,rig)+get_rev(2*idx+1,mid+1,r,lef,rig);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,q,z,t,m;
	cin>>n>>q;
	for(i=1;i<n;i++){
		cin>>lis[i].first>>lis[i].second;
		lis[i].second--;
		lis_rev[n-i]=lis[i];
	}
	for(i=1;i<n;i++){
		lis[i].first-=i;
		lis[i].second-=i;
		lis_rev[i].first-=i;
		lis_rev[i].second-=i;
	}
	if(n==1){
		for(i=1;i<=q;i++){
			cin>>j;
			if(j==1){
				cin>>k>>l>>m;
			}
			else{
				cin>>k>>l>>z>>t;
				cout<<max(0ll,l-t)<<'\n';
			}
		}
		return 0;
	}
	build(1,1,n-1);
	build_rev(1,1,n-1);
	pair<int,int> cac;
	for(i=1;i<=q;i++){
		cin>>j;
		if(j==1){
			cin>>j>>k>>l;
			l--;
			cac={k-j,l-j};
			upd(1,1,n-1,j,cac);
			cac={k-(n-j),l-(n-j)};
			upd_rev(1,1,n-1,n-j,cac);
		}
		else{
			cin>>j>>k>>l>>m;
			if(j==l){
				cout<<max(0ll,k-m)<<'\n';
				continue;
			}
			node ans;
			if(j>l){
				j=(n+1-j);
				l=(n+1-l);
				k-=j;
				m-=l;
				ans=get_rev(1,1,n-1,j,l-1);
			}
			else{
				k-=j;
				m-=l;
				ans=get(1,1,n-1,j,l-1);
			}
            if(k>ans.r){			//time came out
                z=ans.r;
            }
            else{
				if(k>=ans.l){
	                z=k;
	            }
	            else{
	                z=ans.l;
	            }
        	}
			cout<<ans.cost+max(0ll,k-ans.pts)+max(0ll,z-m)<<'\n';
		}
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 30 / 30
• Subtask 3: 66 / 66