Submission #672700

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
672700	2022-12-17T13:46:20 Z	canhnam357	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	597 ms	262256 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 (!root->left) root->left = new node(), lz->left = new node();
	if (!root->right) root->right = new node(), lz->right = new node();
	update(root->left, lz->left, u, v, id << 1, l, mid);
	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	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	19 ms	6320 KB	Output is correct
5	Correct	21 ms	7460 KB	Output is correct
6	Correct	25 ms	7204 KB	Output is correct
7	Correct	22 ms	7500 KB	Output is correct
8	Correct	144 ms	56520 KB	Output is correct
9	Correct	283 ms	101484 KB	Output is correct
10	Correct	324 ms	108328 KB	Output is correct
11	Correct	353 ms	116704 KB	Output is correct
12	Correct	414 ms	120152 KB	Output is correct
13	Correct	319 ms	142476 KB	Output is correct
14	Correct	296 ms	143828 KB	Output is correct
15	Correct	559 ms	261112 KB	Output is correct
16	Runtime error	597 ms	262256 KB	Memory limit exceeded
17	Halted	0 ms	0 KB	-