Submission #594982

#	Time	Username	Problem	Language	Result	Execution time	Memory
594982		balbit	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	862 ms	92924 KiB

timeleap

#include <vector>
#include <bits/stdc++.h>
#define int ll
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
 
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
 
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define pb push_back
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
 
#ifdef BALBIT
#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...);}
#else
#define bug(...)
 
#endif // BALBIT

struct state{
	int L, R; // (-oo, L] maps to Lto, (L,R] maps to y+len, (R, oo) maps to Rto
	int len;
	int Lto, Rto;
	int Lval, Rval; // Lval is Lval, R's value is y+Rval
	pii eval(int y) { // {point to, cost}
		if (y <= L) {
			return {Lto, Lval};
		}
		if (y > R) {
			return {Rto, y + Rval};
		}
		return {y+len, 0};
	}

};

state base(int L, int R) {
	return {L,R-1,1,L+1,R-1+1,0,-(R-1)};
}

state merge (state a, state b){
	state re;
	re.len = a.len + b.len;
	// int oldL=0, oldR=0;
	// bool eq = a.L == a.R;

	if (b.L - a.len >= a.R) {
		a.L = a.R;
	}else if (b.R - a.len <= a.L) {
		a.R = a.L;
	}else{
		MX(a.L, b.L - a.len);
		MN(a.R, b.R - a.len);
	}
	{
		pii ga = b.eval(a.L + a.len);
		pii gb = b.eval(a.R + a.len);
		re.Lto = ga.f, re.Lval = ga.s;
		re.Rto = gb.f, re.Rval = gb.s - a.R;
	}
	re.L = a.L; re.R = a.R;
	return re;
}

const int maxn = 3e5+5;

pii A[maxn];
state s[maxn*4];

void build(int o, int l, int r) {
	if (l == r) {
		s[o] = base(A[l].f, A[l].s);
		return;
	}
	int mid = (l+r)/2;
	build(o*2,l,mid); build(o*2+1,mid+1,r);
	s[o] = merge(s[o*2], s[o*2+1]);
}

pii QU(int L, int R, int pt, int o, int l, int r) {
	if (l > R || r < L) return {pt,0};
	if (l >= L && r <= R) {
		return s[o].eval(pt);
	}
	int mid = (l+r)/2;
	pii gl = QU(L,R,pt,o*2,l,mid);
	pii gr = QU(L,R,gl.f,o*2+1,mid+1,r);
	gr.s += gl.s;
	return gr;
}

void MO(int p, pii v, int o, int l, int r) {
	if (l > p || r < p) return;
	if (l==r) {
		s[o] = base(v.f, v.s);
		return;
	}
	int mid = (l+r)/2;
	MO(p,v,o*2,l,mid); MO(p,v,o*2+1,mid+1,r);
	s[o] = merge(s[o*2], s[o*2+1]);
}

struct query{
	int l, r, t1, t2; // if l == -1, it's a modify operation on point r, range [t1,t2]
};

query ask[maxn];
int ans[maxn];

signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	bug(1,2);

	int n,q; cin>>n>>q;
	REP(i,n-1) {
		cin>>A[i].f>>A[i].s;
	}

	REP(i,q) {
		int T; cin>>T;
		if (T == 1) {
			int p,s,e; cin>>p>>s>>e;
			--p;
			ask[i] = {-1, p, s, e};
		}else{
			int l,r,t1,t2;
			cin>>l>>t1>>r>>t2;
			--l; --r;
			ask[i] = {l,r,t1,t2};
		}
	}
	memset(ans, -1, sizeof ans);
	REP(round, 2) {
		build(1,0,n-1);
		REP(i,q) {
			query Q = ask[i];
			if (Q.l == Q.r) {
				ans[i] = max(0ll, Q.t1 - Q.t2);
			}
			if (Q.l < Q.r) {
				if (Q.l == -1) {
					MO(Q.r, make_pair(Q.t1, Q.t2), 1,0,n-1);
				}else{
					pii ha = QU(Q.l, Q.r-1, Q.t1, 1, 0, n-1);
					bug(i, ha.f, ha.s);
					int re = ha.s + max(0ll, ha.f - Q.t2);
					ans[i] = re;
				}
			}
		}

		reverse(A, A+n-1);
		for (query &qqq : ask) {
			if (qqq.l!=-1) {
				qqq.l = n-qqq.l-1;
			}
			qqq.r = n-qqq.r-1;
		}
	}

	REP(i,q) if (ans[i] != -1) cout<<ans[i]<<endl;
}

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