Submission #757219

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757219	2023-06-12T19:18:51 Z	tcmmichaelb139	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	483 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) {
			if (c[0]) c[0]->lzAdd = lzAdd;
			if (c[1]) 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	1 ms	320 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	17 ms	8668 KB	Output is correct
5	Correct	25 ms	10448 KB	Output is correct
6	Correct	30 ms	10056 KB	Output is correct
7	Correct	27 ms	10444 KB	Output is correct
8	Correct	205 ms	77204 KB	Output is correct
9	Correct	383 ms	131032 KB	Output is correct
10	Correct	379 ms	147120 KB	Output is correct
11	Correct	407 ms	159708 KB	Output is correct
12	Correct	483 ms	165104 KB	Output is correct
13	Correct	398 ms	205248 KB	Output is correct
14	Correct	390 ms	207308 KB	Output is correct
15	Runtime error	461 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-