Submission #957949

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
957949	2024-04-04T14:04:28 Z	bmh123456789asdf	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	319 ms	188500 KB

apple

#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 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[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) {
	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[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);
		}

		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[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	70 ms	185940 KB	Output is correct
2	Correct	56 ms	185980 KB	Output is correct
3	Correct	55 ms	185964 KB	Output is correct
4	Correct	63 ms	186036 KB	Output is correct
5	Correct	69 ms	185960 KB	Output is correct
6	Correct	69 ms	185940 KB	Output is correct
7	Correct	66 ms	186008 KB	Output is correct
8	Correct	147 ms	186892 KB	Output is correct
9	Correct	242 ms	188156 KB	Output is correct
10	Correct	241 ms	187828 KB	Output is correct
11	Correct	239 ms	187888 KB	Output is correct
12	Correct	268 ms	187796 KB	Output is correct
13	Correct	218 ms	188320 KB	Output is correct
14	Correct	230 ms	188500 KB	Output is correct
15	Correct	300 ms	188320 KB	Output is correct
16	Correct	319 ms	188484 KB	Output is correct
17	Correct	244 ms	188460 KB	Output is correct
18	Correct	205 ms	188444 KB	Output is correct
19	Correct	281 ms	188316 KB	Output is correct
20	Correct	280 ms	188488 KB	Output is correct