Submission #745397

#	Time	Username	Problem	Language	Result	Execution time	Memory
745397		t6twotwo	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	44 ms	2976 KiB

apple

//https://oj.uz/submission/337243
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int T = 1E9;
struct Node {
	int s = 0;
	Node *l, *r;
} *r = new Node();
void update(Node *p, int l, int r, int L, int R) {
	if (R <= l || r <= L || p -> s == r - l) {
		return;
	}
	if (L <= l && r <= R) {
		p -> s = r - l;
		return;
	}
	if (!p -> l) {
		p -> l = new Node();
	}
	if (!p -> r) {
		p -> r = new Node();
	}
	int m = (l + r + 1) / 2;
	update(p -> l, l, m, L, R);
	update(p -> r, m, r, L, R);
	p -> s = p -> l -> s + p -> r -> s;
}
int query(Node *p, int l, int r, int L, int R) {
	if (R <= l || r <= L || p -> s == 0) {
		return 0;
	}
	if (p -> s == r - l) {
		return min(r, R) - max(l, L);
	}
	if (L <= l && r <= R) {
		return p -> s;
	}
	int m = (l + r + 1) / 2;
	return query(p -> l, l, m, L, R) + query(p -> r, m, r, L, R);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Q;
	cin >> Q;
	int C = 0;
	while (Q--) {
		int D, X, Y;
		cin >> D >> X >> Y;
		if (D == 1) {
			C = query(r, 1, T + 1, X + C, Y + C + 1);
			cout << C << "\n";
		} else {
			update(r, 1, T + 1, X + C, Y + C + 1);
		}
	}
	return 6/22;
}

• Subtask 1: 100 / 100