Submission #957952

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
957952	2024-04-04T14:07:30 Z	bmh123456789asdf	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	309 ms	186708 KB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define MOD 1000000007
typedef long long ll;
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 = 1;

void pushlazy(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[cnt].tl = segtree[node].tl;
			segtree[cnt].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = ++cnt;
			segtree[cnt].tl = mid + 1;
			segtree[cnt].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) {
	pushlazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr) {
		segtree[node].lazy = 1;
		pushlazy(node);
	} else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = ++cnt;
			segtree[cnt].tl = segtree[node].tl;
			segtree[cnt].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = ++cnt;
			segtree[cnt].tl = mid + 1;
			segtree[cnt].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);
		}

		pushlazy(segtree[node].l);
		pushlazy(segtree[node].r);
		segtree[node].sum =
		    segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
	}
}


int query(int node,int l,int r)
{
	pushlazy(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[cnt].tl = segtree[node].tl;
			segtree[cnt].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = ++cnt;
			segtree[cnt].tl = mid + 1;
			segtree[cnt].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);
	cout.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, d, x, y;
	for(int i = 1; i <= m; i++) {
		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	60 ms	185856 KB	Output is correct
2	Correct	60 ms	185936 KB	Output is correct
3	Correct	63 ms	185936 KB	Output is correct
4	Correct	70 ms	185936 KB	Output is correct
5	Correct	70 ms	185940 KB	Output is correct
6	Correct	76 ms	185988 KB	Output is correct
7	Correct	69 ms	185940 KB	Output is correct
8	Correct	135 ms	185948 KB	Output is correct
9	Correct	229 ms	186176 KB	Output is correct
10	Correct	239 ms	186464 KB	Output is correct
11	Correct	244 ms	186324 KB	Output is correct
12	Correct	230 ms	186192 KB	Output is correct
13	Correct	210 ms	186448 KB	Output is correct
14	Correct	215 ms	186624 KB	Output is correct
15	Correct	309 ms	186448 KB	Output is correct
16	Correct	281 ms	186448 KB	Output is correct
17	Correct	212 ms	186288 KB	Output is correct
18	Correct	208 ms	186448 KB	Output is correct
19	Correct	282 ms	186708 KB	Output is correct
20	Correct	306 ms	186412 KB	Output is correct