Submission #957951

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
957951	2024-04-04T14:06:30 Z	bmh123456789asdf	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	307 ms	187988 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 = 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);
	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	64 ms	185964 KB	Output is correct
2	Correct	61 ms	185936 KB	Output is correct
3	Correct	58 ms	185800 KB	Output is correct
4	Correct	69 ms	186448 KB	Output is correct
5	Correct	68 ms	185936 KB	Output is correct
6	Correct	70 ms	186152 KB	Output is correct
7	Correct	69 ms	186040 KB	Output is correct
8	Correct	151 ms	187084 KB	Output is correct
9	Correct	224 ms	187580 KB	Output is correct
10	Correct	237 ms	187472 KB	Output is correct
11	Correct	235 ms	187400 KB	Output is correct
12	Correct	238 ms	187636 KB	Output is correct
13	Correct	212 ms	187988 KB	Output is correct
14	Correct	207 ms	187684 KB	Output is correct
15	Correct	288 ms	187836 KB	Output is correct
16	Correct	285 ms	187860 KB	Output is correct
17	Correct	208 ms	187732 KB	Output is correct
18	Correct	216 ms	187868 KB	Output is correct
19	Correct	278 ms	187880 KB	Output is correct
20	Correct	307 ms	187732 KB	Output is correct