Submission #757179

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757179	2023-06-12T18:36:58 Z	tcmmichaelb139	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	496 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'000);

	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	1 ms	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	21 ms	11412 KB	Output is correct
5	Correct	26 ms	13848 KB	Output is correct
6	Correct	24 ms	13304 KB	Output is correct
7	Correct	25 ms	13884 KB	Output is correct
8	Correct	201 ms	103536 KB	Output is correct
9	Correct	414 ms	175960 KB	Output is correct
10	Correct	443 ms	197404 KB	Output is correct
11	Correct	445 ms	213968 KB	Output is correct
12	Correct	496 ms	221440 KB	Output is correct
13	Runtime error	410 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-