Submission #757202

#	Time	Username	Problem	Language	Result	Execution time	Memory
757202		tcmmichaelb139	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	212 KiB

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]->lzAdd = lzAdd;
			if (c[1]) 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