oj.uz

Submission #757206

# Submission time Handle Problem Language Result Execution time Memory
757206 2023-06-12T19:09:39 Z tcmmichaelb139 Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 562 ms 262144 KB 
#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 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 16 ms 5776 KB Output is correct
5 Correct 22 ms 7052 KB Output is correct
6 Correct 25 ms 6736 KB Output is correct
7 Correct 21 ms 6988 KB Output is correct
8 Correct 170 ms 51436 KB Output is correct
9 Correct 310 ms 87624 KB Output is correct
10 Correct 348 ms 98124 KB Output is correct
11 Correct 340 ms 106500 KB Output is correct
12 Correct 334 ms 110080 KB Output is correct
13 Correct 321 ms 136948 KB Output is correct
14 Correct 360 ms 138208 KB Output is correct
15 Correct 547 ms 254572 KB Output is correct
16 Correct 562 ms 256612 KB Output is correct
17 Correct 346 ms 145392 KB Output is correct
18 Correct 356 ms 145352 KB Output is correct
19 Correct 560 ms 262144 KB Output is correct
20 Correct 555 ms 262144 KB Output is correct