Submission #218026

#	Time	Username	Problem	Language	Result	Execution time	Memory
218026		manh9203	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	777 ms	91188 KiB

timeleap

#include<bits/stdc++.h>

using namespace std;

#define ll long long
const int N = 3e5 + 5;

int n, q, L[2][N], R[2][N];

struct node{
	ll l, r, pos, cost;
} st[2][4 * N];

node merge(node a, node b){
	node res;
	if(a.l == a.r){
		if(b.l == b.r){
			res.l = res.r = a.l;
			res.pos = b.pos;
			res.cost = a.cost + b.cost + max(0LL, a.pos - b.l);
		} else {
			res.l = res.r = a.l;
			res.pos = min(b.r, max(b.l, a.pos));
			res.cost = a.cost + b.cost + max(0LL, a.pos - b.r);
		}
	} else {
		if(b.l == b.r){
			if(a.r < b.l){
				res.l = res.r = a.r;
				res.pos = b.pos;
				res.cost = a.cost + b.cost;
			} else if(a.l > b.l){
				res.l = res.r = a.l;
				res.pos = b.pos;
				res.cost = a.cost + b.cost + a.pos - b.l;
			} else {
				res.l = res.r = b.l;
				res.pos = b.pos;
				res.cost = a.cost + b.cost;
			}
		} else {
			if(a.r < b.l){
				res.l = res.r = a.r;
				res.pos = b.l;
				res.cost = a.cost + b.cost;
			} else if(a.l > b.r){
				res.l = res.r = a.l;
				res.pos = b.r;
				res.cost = a.cost + b.cost + a.l - b.r; 
			} else {
				res.l = max(a.l, b.l);
				res.r = min(a.r, b.r);
				res.pos = res.l;
				res.cost = 0;
			}
		}
	}
	return res;
}

void build(int id, int l, int r, int t){
	if(l == r){
		st[t][id].l = L[t][l];
		st[t][id].r = R[t][l];
		st[t][id].pos = L[t][l];
		st[t][id].cost = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid, t);
	build(id << 1 | 1, mid + 1, r, t);
	st[t][id] = merge(st[t][id << 1], st[t][id << 1 | 1]);
}

void update(int id, int l, int r, int i, node x, int t){
	if(l > i || r < i){
		return;
	}
	if(l == r){
		st[t][id] = x;
		return;
	}
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, i, x, t);
	update(id << 1 | 1, mid + 1, r, i, x, t);
	st[t][id] = merge(st[t][id << 1], st[t][id << 1 | 1]);
}

node get(int id, int l, int r, int i, int j, int t){
	if(l > j || r < i || i > j){
		return {(ll)-1e9, (ll)1e9, (ll)-1e9, 0};
	}
	if(l >= i && r <= j){
		return st[t][id];
	}
	int mid = (l + r) >> 1;
	return merge(get(id << 1, l, mid, i, j, t), get(id << 1 | 1, mid + 1, r, i, j, t));
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> q;
	
	if(n == 1){
		while(q--){
			int t, a, b, c, d;
			cin >> t;
			if(t == 2){
				cin >> a >> b >> c >> d;
				cout << max(0, b - d) << "\n";
			}
		}
		return 0;
	}
	
	for(int i = 1; i < n; i++){
		cin >> L[0][i] >> R[0][i];
		L[1][n - i] = L[0][i];
		R[1][n - i] = R[0][i];
	}
	for(int i = 1; i < n; i++){
		L[0][i] -= i; R[0][i] -= i + 1;
		L[1][i] -= i; R[1][i] -= i + 1;
	}
	build(1, 1, n - 1, 0);
	build(1, 1, n - 1, 1);
	
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int p, s, e;
			cin >> p >> s >> e;
			node tmp = {s - p, e - p - 1, s - p, 0};
			update(1, 1, n - 1, p, tmp, 0);
			p = n - p;
			tmp = {s - p, e - p - 1, s - p, 0};
			update(1, 1, n - 1, p, tmp, 1);
		} else {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			if(a == c){
				cout << max(0, b - d) << "\n";
			} else {
				int ck = 0;
				if(a > c){
					a = n - a + 1; c = n - c + 1;
					ck = 1;
				}
				node res = get(1, 1, n - 1, a, c - 1, ck);
				b -= a; d -= c;
				res = merge({b, b, b, 0}, res);
				cout << res.cost + max(0LL, res.pos - d) << "\n";
			}
		}
	}
}

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