Submission #757183

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757183	2023-06-12T18:39:25 Z	tcmmichaelb139	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	435 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 push() {
		if (lzAdd == 0) return;
		val = (R - L + 1) * lzAdd;
		if (L != R) {
			if (c[0]) c[0]->lzAdd = lzAdd;
			if (c[1]) c[1]->lzAdd = lzAdd;
		}
		lzAdd = 0;
	}
	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 pull() { val = c[0]->val + c[1]->val; }
	void upd(int lo, int hi, int inc) {
		extend();
		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);
		pull();
	}
	int query(int lo, int hi) {
		extend();
		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	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	18 ms	8532 KB	Output is correct
5	Correct	23 ms	10352 KB	Output is correct
6	Correct	24 ms	9984 KB	Output is correct
7	Correct	25 ms	10276 KB	Output is correct
8	Correct	170 ms	76988 KB	Output is correct
9	Correct	380 ms	130948 KB	Output is correct
10	Correct	395 ms	146844 KB	Output is correct
11	Correct	390 ms	159336 KB	Output is correct
12	Correct	435 ms	164844 KB	Output is correct
13	Correct	372 ms	207200 KB	Output is correct
14	Correct	409 ms	209096 KB	Output is correct
15	Runtime error	427 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-