Submission #1400922

#TimeUsernameProblemLanguageResultExecution timeMemory
1400922limitsMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
31 ms908 KiB
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

struct ST {
	vector<int> sum{0}, L{0}, R{0};
	int root = 0;

	int upd(int ql, int qr, int v, int l, int r) {
		if (qr < l || r < ql || sum[v] == r - l + 1) return v;
		if (!v) {
			v = sum.size();
			sum.pb(0), L.pb(0), R.pb(0);
		}
		if (ql <= l && r <= qr) {
			sum[v] = r-l+1;
			return v;
		}
		int m = (l+r)/2;
		L[v] = upd(ql, qr, L[v], l, m);
		R[v] = upd(ql, qr, R[v], m+1, r);
		sum[v] = (L[v] ? sum[L[v]] : 0) + (R[v] ? sum[R[v]] : 0);
		return v;
	}
	int query(int ql, int qr, int v, int l, int r) {
		if (qr < l || r < ql || !v) return 0;
		if (ql <= l && r <= qr) return sum[v];
		if (sum[v] == r-l+1) {
			return max(min(qr, r) - max(l, ql) + 1, 0);
		}
		int m = (l+r)/2;
		return query(ql, qr, L[v], l, m) + query(ql, qr, R[v], m+1, r);
	}
	void upd(int ql, int qr) {
		root = upd(ql, qr, root, 0, 1e9+5);
	}
	int query(int ql, int qr) {
		return query(ql, qr, root, 0, 1e9+5);
	}
};



int main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	int m;
	cin >> m;

	ST st;
	int t, l, r, c = 0;
	while (m--) {
		cin >> t >> l >> r;
		l += c, r += c;
		if (t == 2) st.upd(l, r);
		else cout << (c = st.query(l, r)) << '\n';
	}
}
#Result Execution timeMemoryGrader output
Fetching results...