Submission #757181

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

apple

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

struct Node {
	long long val;
	long long lzAdd;
	long long L, R;
	Node *c[2];
	Node(long long l, long long 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) {
			long long 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(long long lo, long long hi, long long 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();
	}
	long long query(long long lo, long long hi) {
		extend();
		push();
		if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return val;
		long long 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'001);

	long long 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	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	20 ms	11340 KB	Output is correct
5	Correct	26 ms	13740 KB	Output is correct
6	Correct	24 ms	13140 KB	Output is correct
7	Correct	25 ms	13712 KB	Output is correct
8	Correct	202 ms	102448 KB	Output is correct
9	Correct	444 ms	174196 KB	Output is correct
10	Correct	429 ms	195620 KB	Output is correct
11	Correct	488 ms	212184 KB	Output is correct
12	Correct	481 ms	219532 KB	Output is correct
13	Runtime error	397 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-