Submission #757204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757204	2023-06-12T19:06:49 Z	tcmmichaelb139	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	368 ms	108304 KB

apple

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

const int SZ = 100'000'001;
struct Node {
	int val;
	int lzAdd;
	Node *c[2];
	Node() {
		val = 0;
		lzAdd = 0;
		c[0] = c[1] = NULL;
	}
	void push(int L, int R) {
		if (lzAdd == 0) return;
		val = R - L + 1;
		if (L != R) {
			if (!c[0]) c[0] = new Node();
			c[0]->lzAdd = lzAdd;
			if (!c[1]) c[1] = new Node();
			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;
		if (!c[0]) c[0] = new Node();
		c[0]->upd(lo, hi, inc, L, M);
		if (!c[1]) c[1] = new Node();
		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;
		if (c[0]) res += c[0]->query(lo, hi, L, M);
		if (c[1]) 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	1 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	17 ms	5700 KB	Output is correct
5	Correct	22 ms	6880 KB	Output is correct
6	Correct	21 ms	6584 KB	Output is correct
7	Correct	21 ms	6860 KB	Output is correct
8	Correct	166 ms	50524 KB	Output is correct
9	Correct	303 ms	85872 KB	Output is correct
10	Correct	368 ms	96428 KB	Output is correct
11	Correct	339 ms	104648 KB	Output is correct
12	Correct	364 ms	108304 KB	Output is correct
13	Incorrect	68 ms	19512 KB	Output isn't correct
14	Halted	0 ms	0 KB	-