Submission #757191

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757191	2023-06-12T18:55:10 Z	tcmmichaelb139	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	443 ms	262144 KB

apple

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

struct Node {
	int val;
	int lzAdd;
	int L, R;
	Node *c[2];
	Node(int l, int r) : L(l), R(r) {
		val = 0;
		lzAdd = 0;
		c[0] = c[1] = NULL;
	}
	void extend() {
		if (!c[0] && !c[1] && L != R) {
			int M = (L + R) / 2;
			c[0] = new Node(L, M);
			c[1] = new Node(M + 1, R);
		}
	}
	void push() {
		extend();
		if (lzAdd == 0) return;
		val = R - L + 1;
		if (L != R) {
			c[0]->lzAdd = lzAdd;
			c[1]->lzAdd = lzAdd;
		}
		lzAdd = 0;
	}
	void upd(int lo, int hi, int inc) {
		push();
		if (lo > R || L > hi) return;
		if (lo <= L && R <= hi) {
			lzAdd = inc;
			push();
			return;
		}
		c[0]->upd(lo, hi, inc);
		c[1]->upd(lo, hi, inc);
		val = c[0]->val + c[1]->val;
	}
	int query(int lo, int hi) {
		push();
		if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return val;
		int res = 0;
		res += c[0]->query(lo, hi);
		res += c[1]->query(lo, hi);
		return res;
	}
};

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

	int n;
	cin >> n;

	Node seg(1, 1'000'000'000);

	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			ans = seg.query(b + ans, c + ans);
			cout << ans << '\n';
		} else {
			seg.upd(b + ans, c + ans, 1);
		}
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	20 ms	8540 KB	Output is correct
5	Correct	21 ms	10324 KB	Output is correct
6	Correct	23 ms	9972 KB	Output is correct
7	Correct	22 ms	10328 KB	Output is correct
8	Correct	177 ms	77040 KB	Output is correct
9	Correct	344 ms	130896 KB	Output is correct
10	Correct	362 ms	146936 KB	Output is correct
11	Correct	378 ms	159376 KB	Output is correct
12	Correct	426 ms	164828 KB	Output is correct
13	Correct	373 ms	204976 KB	Output is correct
14	Correct	443 ms	207012 KB	Output is correct
15	Runtime error	413 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-