제출 #672704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672704		canhnam357	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	531 ms	262144 KiB

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