Submission #201633

#	Time	Username	Problem	Language	Result	Execution time	Memory
201633		red1108	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	4 / 100	599 ms	74104 KiB

timeleap

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;typedef long double ld;typedef unsigned long long ul;typedef unsigned int ui;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cerr << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cerr << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cerr << endl;}

int n,q,in[300010][2];
struct Node{
	ll b;
	int x,ls,le,rs,re,si;
	Node(){};
	Node(ll bb,int xx,int i,int j,int k,int l){b=bb;x=xx;ls=i;le=j;rs=k;re=l;si=0;}
	Node operator +(Node B){
		B.x--;B.ls--;B.le--;
		Node p = Node(b,x,ls,le,rs,re);
		if(p.re>B.x&&B.x>=p.rs) p.x-=(p.re-B.x);
		else if(p.rs>B.x){
			if(p.rs!=p.re) p.x = p.rs - si;
			p.b+=(p.rs-B.x);
		}
		p.b+=B.b;	
		p.si = si + B.si + 1;
		if(B.re==B.rs){
			p.rs=B.rs;
			p.re=B.re;
			return p;
		}
		ll t = B.re-B.rs, ss = B.rs-B.si-1, ee = B.re-B.si-1;
		if(p.rs<=ss) p.rs=B.rs;
		else if(p.rs>=ee) p.rs=B.re;
		else p.rs = B.rs + min(t,p.rs-ss);
		if(p.re<=ss) p.re=B.rs;
		else if(p.re>=ee) p.re=B.re;
		else p.re = B.rs + min(t,p.re-ss);
		return p;
	}
};
vector<Node> help;
struct SEG{
	Node val[1201000];
	void init(int x, int l, int r, bool t){
		if(l==r){
			if(t)val[x]=Node(0,in[l][1],in[l][0],in[l][1],in[l][0],in[l][1]);
			else val[x]=Node(0,in[n-l][1],in[n-l][0],in[n-l][1],in[n-l][0],in[n-l][1]);
			return ;
		}
		init(x*2,l,(l+r)/2,t);
		init(x*2+1,(l+r)/2+1,r,t);
		val[x]=val[x*2]+val[x*2+1];
	}
	void gang(int x, int l, int r, int ind, bool t){
		if(r<ind||ind<l) return ;
		if(l==r){
			if(t)val[x]=Node(0,in[l][1],in[l][0],in[l][1],in[l][0],in[l][1]);
			else val[x]=Node(0,in[n-l][1],in[n-l][0],in[n-l][1],in[n-l][0],in[n-l][1]);
			return ;
		}
		gang(x*2,l,(l+r)/2,ind,t);
		gang(x*2+1,(l+r)/2+1,r,ind,t);
		val[x]=val[x*2]+val[x*2+1];
	}
	void query(int x, int l, int r,int s, int e){
		if(r<s||e<l) return ;
		if(s<=l&&r<=e){
			help.eb(val[x]);return ;
		}
		query(x*2,l,(l+r)/2,s,e);
		query(x*2+1,(l+r)/2+1,r,s,e);
	}
}seg1, seg2;
ll eval(int s, int e){
	for(int i=help.size()-2;i>=0;i--) help[i]=help[i]+help[i+1];
	s = max(help[0].ls,s);
	ll ret = help[0].b + max(s-help[0].x,0);
	if(help[0].rs==help[0].re){
		ret+=max(help[0].re+1-e,0);
		return ret;
	}
	int ss = help[0].rs-help[0].si, t = help[0].rs+1;
	if(s>ss) t = help[0].rs + min(help[0].re-help[0].rs,s-ss)+1;
	ret+=max(t-e,0);
	return ret;
}
int main(){
	//fopen;
	fastio;
	cin>>n>>q;
	for(int i=1;i<n;i++){
		cin>>in[i][0]>>in[i][1];
		in[i][1]--;
	}
	if(n==1){
		while(q--){
			int a,b,c,d;
			cin>>a;
			if(a==1){cin>>a>>b>>c;}
			else if(a==2){
				cin>>a>>b>>c>>d;
				cout<<max(b-d,0)<<"\n";
			}
		}
		return 0;
	}
	seg1.init(1,1,n-1,1);
	seg2.init(1,1,n-1,0);
	while(q--){
		int a,b,c,d;
		cin>>a;
		if(a==1){
			cin>>a>>b>>c;
			in[a][0]=b;in[a][1]=c-1;
			seg1.gang(1,1,n-1,a,1);
			seg2.gang(1,1,n-1,n-a,0);
		}
		else{
			cin>>a>>b>>c>>d;
			help.clear();
			ll ans=0;
			if(a<c){
				seg1.query(1,1,n-1,a,c-1);
				ans = eval(b,d);
			}
			else if(a>c){
				a = n-a;c = n-c;
				seg2.query(1,1,n-1,a+1,c);
				ans = eval(b,d);
			}
			else ans = max(b-d,0);
			cout<<ans<<"\n";
		}
	}
}

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