Submission #872366

#	Time	Username	Problem	Language	Result	Execution time	Memory
872366		qthang2k11	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	556 ms	61160 KiB

timeleap

// [+]
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 3e5 + 5;

int n, q;

struct Node {
	int a, b; 
	bool t;
	ll val;
	Node() { val = -1; }
	Node(int l, int r): 
		a(l), b(r), t(true), val(0) {}
	Node(int a, int b, bool t, ll val):
		a(a), b(b), t(t), val(val) {}
};

Node merge(const Node &x, const Node &y) {
	if (x.t) {
		if (y.t) {
			// (1, 1)
			if (x.b < y.a) {
				return Node(x.b, y.a, 0, 0);
			} else if (y.b < x.a) {
				return Node(x.a, y.b, 0, x.a - y.b);
			} else {
				return Node(max(x.a, y.a), min(x.b, y.b), 1, 0);
			}
		} else { 
			return Node(max(x.a, min(x.b, y.a)), y.b, 0, y.val + max(0, x.a - y.a)); // (1, 0)
		}
	} else {
		if (y.t) {
			return Node(x.a, max(y.a, min(x.b, y.b)), 0, x.val + max(0, x.b - y.b)); // (0, 1)
		} else {
			return Node(x.a, y.b, 0, x.val + y.val + max(0, x.b - y.a)); // (0, 0)
		}
	}
}

struct SegmentTree {
	Node IT[N << 2];
	SegmentTree() {}
	
	void update(int x, int L, int R, int id, int l, int r) {
		if (l == r) return IT[id] = Node(L, R), void();
		int mid = (l + r) / 2;
		if (x <= mid) update(x, L, R, id << 1, l, mid);
		else update(x, L, R, id << 1 | 1, mid + 1, r);
		IT[id] = merge(IT[id << 1], IT[id << 1 | 1]);
	}
	
	inline void update(int x, int l, int r) {
		update(x, l - x, r - x - 1, 1, 1, n - 1);
	}
	
	Node get(int x, int y, int id, int l, int r) {
		if (l > y || r < x) return Node();
		if (x <= l && r <= y) return IT[id];
		int mid = (l + r) / 2;
		auto L = get(x, y, id << 1, l, mid);
		auto R = get(x, y, id << 1 | 1, mid + 1, r);
		if (L.val < 0) return R;
		if (R.val < 0) return L;
		return merge(L, R);
	}
	
	inline Node get(int x, int y) {
		return get(x, y, 1, 1, n - 1);
	}
} seg, revseg;

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> n >> q;
	for (int i = 1; i < n; i++) {
		int l, r; cin >> l >> r;
		seg.update(i, l, r);
		revseg.update(n - i, l, r);
	}
	
	while (q--) {
		int T; cin >> T;
		if (T == 1) {
			int pos, l, r; 
			cin >> pos >> l >> r;
			seg.update(pos, l, r);
			revseg.update(n - pos, l, r);
		} else {
			int A, t_A, B, t_B;
			cin >> A >> t_A >> B >> t_B;
			if (A == B) cout << max(0, t_A - t_B);
			else {
				if (A < B) {
					cout << merge(Node(t_A - A, t_A - A), 
												merge(seg.get(A, B - 1), 
															Node((int)-1e9, t_B - B))).val;
				} else {
					cout << merge(Node(t_A - (n - A + 1), t_A - (n - A + 1)), 
												merge(revseg.get(n - A + 1, n - B), 
															Node((int)-1e9, t_B - (n - B + 1)))).val;
				}
			}
			cout << '\n';
		}
	}
	
	return 0;
}

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