Submission #745397

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
745397	2023-05-20T01:12:26 Z	t6twotwo	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	44 ms	2976 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	4 ms	448 KB	Output is correct
5	Correct	5 ms	468 KB	Output is correct
6	Correct	6 ms	468 KB	Output is correct
7	Correct	5 ms	456 KB	Output is correct
8	Correct	17 ms	1356 KB	Output is correct
9	Correct	34 ms	2408 KB	Output is correct
10	Correct	35 ms	2380 KB	Output is correct
11	Correct	44 ms	2460 KB	Output is correct
12	Correct	41 ms	2468 KB	Output is correct
13	Correct	40 ms	2764 KB	Output is correct
14	Correct	38 ms	2804 KB	Output is correct
15	Correct	32 ms	2948 KB	Output is correct
16	Correct	35 ms	2972 KB	Output is correct
17	Correct	30 ms	2764 KB	Output is correct
18	Correct	30 ms	2876 KB	Output is correct
19	Correct	32 ms	2892 KB	Output is correct
20	Correct	37 ms	2976 KB	Output is correct