Submission #672704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
672704	2022-12-17T13:52:26 Z	canhnam357	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	531 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int val;
	node *left, *right;
	node()
	{
		val = 0;
		left = NULL;
		right = NULL;
	}
	node(int _val)
	{
		val = _val;
		left = NULL;
		right = NULL;
	}
};
node *st = new node(), *lazy = new node();
void push(node *root, node *lz, int sz)
{
	if (root->left)
	{
		root->left->val = sz;
	}
	else
	{
		root->left = new node(sz);
	}
	if (root->right)
	{
		root->right->val = sz;
	}
	else
	{
		root->right = new node(sz);
	}
	if (lz->left)
	{
		lz->left->val = 1;
	}
	else
	{
		lz->left = new node(1);
	}
	if (lz->right)
	{
		lz->right->val = 1;
	}
	else
	{
		lz->right = new node(1);
	}
	lz->val = 0;
}
void update(node *root, node* lz, int u, int v, int id = 1, int l = 1, int r = 1 << 30)
{
	if (r < u || l > v) return;
	if (l >= u && r <= v)
	{
		if (root)
		{
			root->val = r - l + 1;
		}
		else
		{
			root = new node(r - l + 1);
		}
		if (lz)
		{
			lz->val = 1;
		}
		else
		{
			lz = new node(1);
		}
		return;
	}
	if (lz && lz->val)
	{
		push(root, lz, (r - l + 1) / 2);
	}
	int mid = (l + r) >> 1;
	if (u <= mid)
	{
		if (!root->left) root->left = new node(), lz->left = new node();
		update(root->left, lz->left, u, v, id << 1, l, mid);
	}
	if (v > mid)
	{
		if (!root->right) root->right = new node(), lz->right = new node();
		update(root->right, lz->right, u, v, id << 1 | 1, mid + 1, r);
	}
	root->val = (root->left ? root->left->val : 0LL) + (root->right ? root->right->val : 0LL);
}
int get(node *root, node *lz, int u, int v, int id = 1, int l = 1, int r = 1 << 30)
{
	if (r < u || l > v) return 0;
	if (l >= u && r <= v) return root->val;
	if (lz && lz->val)
	{
		push(root, lz, (r - l + 1) / 2);
	}
	int mid = (l + r) >> 1;
	int ans = 0;
	if (root->left) ans += get(root->left, lz->left, u, v, id << 1, l, mid);
	if (root->right) ans += get(root->right, lz->right, u, v, id << 1 | 1, mid + 1, r);
	return ans;
}
int c = 0;
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin >> q;
	while (q--)
	{
		int t, l, r;
		cin >> t >> l >> r;
		l += c, r += c;
		if (t == 1)
		{
			c = get(st, lazy, l, r);
			cout << c << '\n';
		}
		else
		{
			update(st, lazy, l, r);
		}
	}
	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	14 ms	6080 KB	Output is correct
5	Correct	16 ms	7380 KB	Output is correct
6	Correct	18 ms	7144 KB	Output is correct
7	Correct	18 ms	7420 KB	Output is correct
8	Correct	152 ms	55608 KB	Output is correct
9	Correct	277 ms	99672 KB	Output is correct
10	Correct	341 ms	106660 KB	Output is correct
11	Correct	309 ms	114820 KB	Output is correct
12	Correct	375 ms	118388 KB	Output is correct
13	Correct	298 ms	140392 KB	Output is correct
14	Correct	295 ms	141568 KB	Output is correct
15	Correct	499 ms	258908 KB	Output is correct
16	Correct	521 ms	260960 KB	Output is correct
17	Correct	335 ms	146524 KB	Output is correct
18	Correct	298 ms	146552 KB	Output is correct
19	Runtime error	531 ms	262144 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-