Submission #919432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919432	2024-01-31T18:15:04 Z	ilef	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	296 ms	188976 KB

apple

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
struct Node {
	int sum, lazy, tl, tr, l, r;
	Node() : sum(0), lazy(0), l(-1), r(-1) {}
};
const int MAXN = 123456;
Node segtree[64 * MAXN];
int cnt = 2;
void push_lazy(int node) {
	if (segtree[node].lazy) {
		segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
		segtree[node].lazy = 0;
	}
}
void update(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr) {
		segtree[node].lazy = 1;
		push_lazy(node);
	} else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		if (l > mid) update(segtree[node].r, l, r);
		else if (r <= mid) update(segtree[node].l, l, r);
		else {
			update(segtree[node].l, l, mid);
			update(segtree[node].r, mid + 1, r);
		}
		push_lazy(segtree[node].l);
		push_lazy(segtree[node].r);
		segtree[node].sum =
		    segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
	}
}
int query(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr)
		return segtree[node].sum;
	else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		if (l > mid) return query(segtree[node].r, l, r);
		else if (r <= mid) return query(segtree[node].l, l, r);
		else
			return query(segtree[node].l, l, mid) +
			       query(segtree[node].r, mid + 1, r);
	}
}
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int m;
	cin >> m;
	segtree[1].sum = 0;
	segtree[1].lazy = 0;
	segtree[1].tl = 1;
	segtree[1].tr = 1e9;
	int c = 0;
	while(m--) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 1) {
			c = query(1, x + c, y + c);
			cout << c << '\n';
		} else update(1, x + c, y + c);
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	185760 KB	Output is correct
2	Correct	31 ms	185944 KB	Output is correct
3	Correct	35 ms	185948 KB	Output is correct
4	Correct	39 ms	185952 KB	Output is correct
5	Correct	44 ms	186192 KB	Output is correct
6	Correct	49 ms	185996 KB	Output is correct
7	Correct	43 ms	186132 KB	Output is correct
8	Correct	115 ms	186960 KB	Output is correct
9	Correct	244 ms	187844 KB	Output is correct
10	Correct	236 ms	188132 KB	Output is correct
11	Correct	233 ms	188144 KB	Output is correct
12	Correct	222 ms	188104 KB	Output is correct
13	Correct	188 ms	188496 KB	Output is correct
14	Correct	191 ms	188756 KB	Output is correct
15	Correct	282 ms	188432 KB	Output is correct
16	Correct	296 ms	188652 KB	Output is correct
17	Correct	197 ms	188772 KB	Output is correct
18	Correct	205 ms	188480 KB	Output is correct
19	Correct	273 ms	188812 KB	Output is correct
20	Correct	289 ms	188976 KB	Output is correct