Submission #672703

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

apple

#include <bits/stdc++.h>
using namespace std;
#define int long long
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	1 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	15 ms	6124 KB	Output is correct
5	Correct	24 ms	7288 KB	Output is correct
6	Correct	22 ms	7136 KB	Output is correct
7	Correct	19 ms	7380 KB	Output is correct
8	Correct	139 ms	55736 KB	Output is correct
9	Correct	332 ms	99676 KB	Output is correct
10	Correct	306 ms	106548 KB	Output is correct
11	Correct	324 ms	114888 KB	Output is correct
12	Correct	333 ms	118400 KB	Output is correct
13	Correct	313 ms	140364 KB	Output is correct
14	Correct	352 ms	141572 KB	Output is correct
15	Correct	490 ms	258896 KB	Output is correct
16	Correct	496 ms	262008 KB	Output is correct
17	Correct	301 ms	148600 KB	Output is correct
18	Correct	283 ms	148744 KB	Output is correct
19	Runtime error	524 ms	262144 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-