Submission #791307

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
791307	2023-07-24T01:02:13 Z	lukehsiao	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	318 ms	139508 KB

apple

#include <bits/stdc++.h>
using namespace std;

struct node {
	int sum;
	bool lz;
	node* c[2];
	node() {
		sum = 0;
		lz = false;
		c[0] = c[1] = NULL;
	}
	void push(int l, int mid, int r) {
		if (lz) {
			c[0]->sum = mid-l+1;
			c[1]->sum = r-mid;
			c[0]->lz = c[1]->lz = true;
			lz = false;
		}
	}
	void upd(int a, int b, int l=0, int r=1e9-1) {
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			sum = r-l+1;
			lz = true;
		} else {
			int mid = (l+r)/2;
			if (!c[0]) c[0] = new node();
			if (!c[1]) c[1] = new node();
			push(l, mid, r);
			c[0]->upd(a, b, l, mid);
			c[1]->upd(a, b, mid+1, r);
			sum = c[0]->sum + c[1]->sum;
		}
	}
	int qry(int a, int b, int l=0, int r=1e9-1) {
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return sum;
		int mid = (l+r)/2;
		if (!c[0]) c[0] = new node();
		if (!c[1]) c[1] = new node();
		push(l, mid, r);
		return c[0]->qry(a, b, l, mid) + c[1]->qry(a, b, mid+1, r);
	}
};

int m, c;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	node root = node();

	cin >> m;
	for (int i=0, d, x, y; i<m; ++i) {
		cin >> d >> x >> y;
		if (d == 1) {
			c = root.qry(x+c-1, y+c-1);
			cout << c << '\n';
		} else {
			root.upd(x+c-1, y+c-1);
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	8 ms	3428 KB	Output is correct
5	Correct	11 ms	4172 KB	Output is correct
6	Correct	10 ms	4052 KB	Output is correct
7	Correct	11 ms	4180 KB	Output is correct
8	Correct	78 ms	30140 KB	Output is correct
9	Correct	168 ms	52320 KB	Output is correct
10	Correct	172 ms	57772 KB	Output is correct
11	Correct	192 ms	61956 KB	Output is correct
12	Correct	190 ms	63832 KB	Output is correct
13	Correct	167 ms	74180 KB	Output is correct
14	Correct	179 ms	74972 KB	Output is correct
15	Correct	289 ms	135476 KB	Output is correct
16	Correct	318 ms	136440 KB	Output is correct
17	Correct	174 ms	77516 KB	Output is correct
18	Correct	169 ms	77456 KB	Output is correct
19	Correct	279 ms	139420 KB	Output is correct
20	Correct	282 ms	139508 KB	Output is correct