Submission #872365

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

timeleap

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

using ll = long long;

const ll INF = 1e18;

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) {/*fprintf(stderr,"to (%d, %d, %d, %lld)\n",a,b,t,val);*/}
};

Node merge(const Node &x, const Node &y) {
	// fprintf(stderr, "from (%d, %d, %d, %lld) and (%d, %d, %d, %lld)\n", x.a,x.b,x.t,x.val,y.a,y.b,y.t,y.val);
	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);
		// cerr << l << ' ' << mid << " | " << mid + 1 << ' ' << r << '\n';
		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) {
			// auto S = IT[id];
			// cerr << "at range(" << l << ", " << r << ") = ";
			// cerr << S.a << ' ' << S.b << ' ' << S.t << ' ' << S.val << '\n';
			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);
		// cerr << l << ' ' << mid << " | " << mid + 1 << ' ' << r << '\n';
		if (L.val < 0) return R;
		if (R.val < 0) return L;
		return merge(L, R);
	}
	
	inline Node get(int x, int y) {
		
		// auto S = get(x, y, 1, 1, n - 1);
		// fprintf(stderr, "get(%d, %d) = {%d, %d, %d, %lld}\n", x, y, S.a, S.b, S.t, S.val);
		
		return get(x, y, 1, 1, n - 1);
	}
} seg, revseg;

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	
	// merge(Node(2, 4, 1, 0), Node(-1, 1, 1, 0));
	// cerr << "wtf\n\n";
	
	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);
		// cerr << string(10, '>') <<  "at i = " << n - i << ' ' << l - (n - i) << ' ' << r - (n - i) << '\n';
		// cerr << '\n';
	}
	
	// cerr << '\n';
	
	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;
				}
				
				// cerr << n - A + 1 << ' ' << n - B << '\n';
				
				// cerr << S.a << ' ' << S.b << ' ' << S.t << ' ' << S.val << '\n';
				
				
			}
			cout << '\n';
		}
	}
	
	return 0;
}

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