Submission #757199

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757199	2023-06-12T19:03:00 Z	tcmmichaelb139	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	538 ms	262144 KB

apple

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

const int SZ = 1'000'000'001;
;
struct Node {
	int val;
	int lzAdd;
	Node *c[2];
	Node() {
		val = 0;
		lzAdd = 0;
		c[0] = c[1] = NULL;
	}
	void extend() {
		if (!c[0] && !c[1]) {
			c[0] = new Node();
			c[1] = new Node();
		}
	}
	void push(int L, int R) {
		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, int L = 0, int R = SZ - 1) {
		push(L, R);
		if (lo > R || L > hi) return;
		if (lo <= L && R <= hi) {
			lzAdd = inc;
			push(L, R);
			return;
		}
		int M = (L + R) / 2;
		c[0]->upd(lo, hi, inc, L, M);
		c[1]->upd(lo, hi, inc, M + 1, R);
		val = c[0]->val + c[1]->val;
	}
	int query(int lo, int hi, int L = 0, int R = SZ - 1) {
		push(L, R);
		if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return val;
		int M = (L + R) / 2;
		int res = 0;
		res += c[0]->query(lo, hi, L, M);
		res += c[1]->query(lo, hi, M + 1, R);
		return res;
	}
};

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

	int n;
	cin >> n;

	Node seg;

	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	0 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	17 ms	6356 KB	Output is correct
5	Correct	20 ms	7660 KB	Output is correct
6	Correct	21 ms	7404 KB	Output is correct
7	Correct	21 ms	7680 KB	Output is correct
8	Correct	156 ms	58016 KB	Output is correct
9	Correct	379 ms	100608 KB	Output is correct
10	Correct	344 ms	111272 KB	Output is correct
11	Correct	340 ms	119756 KB	Output is correct
12	Correct	363 ms	123356 KB	Output is correct
13	Correct	330 ms	143632 KB	Output is correct
14	Correct	322 ms	145068 KB	Output is correct
15	Runtime error	538 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-