Submission #1028044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028044		danitro	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	103 ms	3156 KiB

apple

#include <bits/stdc++.h>

using namespace std;

long long q, t, a, b, c;

struct nd
{
	long long l, r, val = 0;
	nd *left = NULL, *right = NULL;
	bool full = false;
	
	nd(long long _l = 1, long long _r = 1e9, long long _val = 0)
	{
		l = _l;
		r = _r;
		val = _val;
	}
} *root = new nd();


void update(nd* node, long long l, long long r, long long ql, long long qr)
{
	if(ql > r || l > qr || node -> full)return ;
	if(ql <= l && r <= qr)
	{
		node -> full = true;
		node -> val = r - l + 1;
		return ;
	}
	
	int mid = (l + r) / 2;
	if(node -> left == NULL)node -> left = new nd(l, mid);
	if(node -> right == NULL)node -> right = new nd(mid + 1, r);
	update(node -> left, l, mid, ql, qr);
	update(node -> right, mid + 1, r, ql, qr);
	node -> val = node -> left -> val + node -> right -> val;
	return;
}

long long query(nd* node, long long l, long long r, long long ql, long long qr)
{
	if(node == NULL)return 0;
	if(ql > r || l > qr)return 0;
	if(ql <= l && r <= qr)
	{
		return node -> val;
	}
	if(node -> full)return (min(r, qr) - max(l, ql) + 1);
	int mid = (l + r) / 2;
	//if(node -> left == NULL)node -> left = new nd(l, mid);
	//if(node -> right == NULL)node -> right = new nd(mid + 1, r);
	return query(node -> left, l, mid, ql, qr) + query(node -> right, mid + 1, r, ql, qr);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> q;
	
	for(int i = 0; i < q; i++)
	{
		cin >> t >> a >> b;
		if(t == 1)
		{
			c = query(root, 1, 1e9, a + c, b + c);
			cout << c << endl;
		}
		else
		{
			update(root, 1, 1e9, a + c, b + c);
		}
	}
	
	return 0;
}

• Subtask 1: 100 / 100