Submission #547951

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547951	2022-04-12T04:26:05 Z	Mazaalai	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	401 ms	207744 KB

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 || 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

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	0 ms	212 KB	Output is correct
4	Correct	11 ms	4820 KB	Output is correct
5	Correct	14 ms	5872 KB	Output is correct
6	Correct	14 ms	5604 KB	Output is correct
7	Correct	14 ms	5816 KB	Output is correct
8	Correct	108 ms	43696 KB	Output is correct
9	Correct	232 ms	75564 KB	Output is correct
10	Correct	245 ms	83628 KB	Output is correct
11	Correct	250 ms	89828 KB	Output is correct
12	Correct	252 ms	92680 KB	Output is correct
13	Correct	227 ms	107892 KB	Output is correct
14	Correct	223 ms	108908 KB	Output is correct
15	Correct	362 ms	201808 KB	Output is correct
16	Correct	363 ms	203156 KB	Output is correct
17	Correct	227 ms	114776 KB	Output is correct
18	Correct	229 ms	114824 KB	Output is correct
19	Correct	358 ms	207744 KB	Output is correct
20	Correct	401 ms	207736 KB	Output is correct