Submission #959641

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
959641	2024-04-08T14:52:37 Z	maxFedorchuk	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	35 ms	3164 KB

apple

#include <bits/stdc++.h>
using namespace std;

struct ver
{
	int l;
	int r;

	int cnt;
	int rd;

	int lson;
	int rson;
};

vector < ver > mas;

void upd(int in,int l,int r)
{
	ver zar=mas[in];

	if((zar.r<l || r<zar.l) || zar.rd)
	{
		return;
	}

	if(l<=zar.l && zar.r<=r)
	{
		mas[in].cnt=(zar.r-zar.l+1);
		mas[in].rd=1;
		return;
	}

	if(!zar.lson)
	{
		int mid=(zar.l+zar.r)/2;

		mas[in].lson=zar.lson=mas.size();
		mas.push_back({zar.l,mid,0,0,0,0});

		mas[in].rson=zar.rson=mas.size();
		mas.push_back({mid+1,zar.r,0,0,0,0});
	}

	upd(zar.lson,l,r);
	upd(zar.rson,l,r);

	mas[in].cnt=zar.cnt=mas[zar.lson].cnt+mas[zar.rson].cnt;
	mas[in].rd=zar.rd=(zar.cnt==(zar.r-zar.l+1));
}

int fget(int in,int l,int r)
{
	ver zar=mas[in];
	
	if((zar.r<l || r<zar.l))
	{
		return 0;
	}

	if(zar.cnt==0 || zar.rd)
	{
		return ((min(zar.r,r)-max(zar.l,l)+1)*zar.rd);
	}

	return (fget(zar.lson,l,r)+fget(zar.rson,l,r));
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	mas.push_back({1,int(1e9),0,0,0,0});

	int n,munans=0;
	cin>>n;

	for(int i=1;i<=n;i++)
	{
		int zp,l,r;
		cin>>zp>>l>>r;

		l+=munans;
		r+=munans;

		if(zp==1)
		{
			munans=fget(0,l,r);
			cout<<munans<<"\n";
		}
		else
		{
			upd(0,l,r);
		}
	}

	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Correct	4 ms	656 KB	Output is correct
6	Correct	4 ms	604 KB	Output is correct
7	Correct	4 ms	600 KB	Output is correct
8	Correct	17 ms	1372 KB	Output is correct
9	Correct	32 ms	2496 KB	Output is correct
10	Correct	32 ms	2572 KB	Output is correct
11	Correct	30 ms	2556 KB	Output is correct
12	Correct	30 ms	2388 KB	Output is correct
13	Correct	35 ms	2908 KB	Output is correct
14	Correct	35 ms	2896 KB	Output is correct
15	Correct	27 ms	2908 KB	Output is correct
16	Correct	34 ms	3044 KB	Output is correct
17	Correct	24 ms	2884 KB	Output is correct
18	Correct	24 ms	2904 KB	Output is correct
19	Correct	29 ms	3164 KB	Output is correct
20	Correct	27 ms	3156 KB	Output is correct