Submission #547949

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547949	2022-04-12T04:23:18 Z	Mazaalai	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	350 ms	262144 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	9468 KB	Output is correct
5	Correct	20 ms	11376 KB	Output is correct
6	Correct	19 ms	10976 KB	Output is correct
7	Correct	19 ms	11296 KB	Output is correct
8	Correct	153 ms	86988 KB	Output is correct
9	Correct	311 ms	150472 KB	Output is correct
10	Correct	324 ms	166584 KB	Output is correct
11	Correct	350 ms	179084 KB	Output is correct
12	Correct	340 ms	184780 KB	Output is correct
13	Correct	327 ms	215260 KB	Output is correct
14	Correct	314 ms	217092 KB	Output is correct
15	Runtime error	350 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-