Submission #1028044

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028044	2024-07-19T12:49:49 Z	danitro	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	103 ms	3156 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	7 ms	604 KB	Output is correct
5	Correct	8 ms	652 KB	Output is correct
6	Correct	12 ms	644 KB	Output is correct
7	Correct	12 ms	604 KB	Output is correct
8	Correct	38 ms	1324 KB	Output is correct
9	Correct	74 ms	2388 KB	Output is correct
10	Correct	90 ms	2388 KB	Output is correct
11	Correct	90 ms	2512 KB	Output is correct
12	Correct	75 ms	2532 KB	Output is correct
13	Correct	90 ms	2896 KB	Output is correct
14	Correct	83 ms	2896 KB	Output is correct
15	Correct	103 ms	3120 KB	Output is correct
16	Correct	79 ms	2944 KB	Output is correct
17	Correct	69 ms	2896 KB	Output is correct
18	Correct	74 ms	2900 KB	Output is correct
19	Correct	90 ms	3156 KB	Output is correct
20	Correct	78 ms	3156 KB	Output is correct