Submission #547947

#	Time	Username	Problem	Language	Result	Execution time	Memory
547947		Mazaalai	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	505 ms	262144 KiB

apple

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int QUERY = 1;
struct Node {
	int val, l, r;
	bool lazy;
	Node* child[2];
	void addSide() {
		int mid = (l+r)>>1;
		if (!child[0]) child[0] = new Node(l, mid);
		if (!child[1]) child[1] = new Node(mid+1, r);
	}
	void fill() {
		val = r - l + 1;
		lazy = 1;
		addSide();
	}
	Node(int _l, int _r) {
		l = _l, r = _r;
		val = lazy = 0;
		child[0] = child[1] = NULL;
	}
};
Node* root = new Node(1, 1e9);
void propagate(Node* node) {
	if (!node->lazy) return;
	node->lazy = 0;
	node->child[0]->lazy = 1;
	node->child[0]->fill();
	node->child[1]->lazy = 1;
	node->child[1]->fill();
}
void update(int l, int r, Node* node) {
	if (node->l > r || l > node->r) return;
	if (l <= node->l && node->r <= r) {
		node->fill();
		return;
	}
	node->addSide();
	propagate(node);
	update(l, r, node->child[0]);
	update(l, r, node->child[1]);
	node->val = node->child[0]->val + node->child[1]->val;
}
int query(int l, int r, Node* node) {
	if (node->l > r || l > node->r || node->l > node->r) return 0;
	if (l <= node->l && node->r <= r) return node->val;
	node->addSide();
	propagate(node);
	return (
		query(l, r, node->child[0]) +
		query(l, r, node->child[1])
	);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> q;
	int c = 0;
	// root = new Node(1, 1e9);
	for (int i = 1; i <= q; i++) {
		int t, a, b; cin >> t >> a >> b;
		if (t == QUERY) {
			c = query(a+c, b+c, root);
			cout << c << '\n';
		} else {
			update(a+c, b+c, root);
		}
	}
}

• Subtask 1: 0 / 100