Submission #442055

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442055	2021-07-06T23:52:32 Z	penguinhacker	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	474 ms	186356 KB

apple

// NOT MY CODE (used usaco.guide to see memory performance)
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#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 = 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;
	FOR(_, 0, 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	88 ms	185796 KB	Output is correct
2	Correct	90 ms	185828 KB	Output is correct
3	Correct	90 ms	185796 KB	Output is correct
4	Correct	116 ms	185796 KB	Output is correct
5	Correct	129 ms	185828 KB	Output is correct
6	Correct	107 ms	185828 KB	Output is correct
7	Correct	108 ms	185960 KB	Output is correct
8	Correct	219 ms	186016 KB	Output is correct
9	Correct	374 ms	186328 KB	Output is correct
10	Correct	374 ms	186180 KB	Output is correct
11	Correct	391 ms	186220 KB	Output is correct
12	Correct	384 ms	186100 KB	Output is correct
13	Correct	340 ms	186308 KB	Output is correct
14	Correct	337 ms	186292 KB	Output is correct
15	Correct	451 ms	186308 KB	Output is correct
16	Correct	457 ms	186328 KB	Output is correct
17	Correct	363 ms	186356 KB	Output is correct
18	Correct	341 ms	186308 KB	Output is correct
19	Correct	474 ms	186244 KB	Output is correct
20	Correct	463 ms	186328 KB	Output is correct