Submission #547947

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547947	2022-04-12T04:20:22 Z	Mazaalai	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	505 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->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	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	20 ms	9484 KB	Output is correct
5	Correct	25 ms	11560 KB	Output is correct
6	Correct	26 ms	11100 KB	Output is correct
7	Correct	25 ms	11512 KB	Output is correct
8	Correct	189 ms	87768 KB	Output is correct
9	Correct	407 ms	152220 KB	Output is correct
10	Correct	424 ms	168348 KB	Output is correct
11	Correct	505 ms	180764 KB	Output is correct
12	Correct	406 ms	186584 KB	Output is correct
13	Correct	363 ms	217136 KB	Output is correct
14	Correct	371 ms	219160 KB	Output is correct
15	Runtime error	398 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-