Submission #959643

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
959643	2024-04-08T14:53:22 Z	maxFedorchuk	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	34 ms	868 KB

apple

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

#pragma GCC target("avx2,sse4,popcnt,bmi")
#pragma GCC optimize("Ofast,unroll-loops")

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	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	3 ms	348 KB	Output is correct
5	Correct	4 ms	348 KB	Output is correct
6	Correct	4 ms	468 KB	Output is correct
7	Correct	4 ms	348 KB	Output is correct
8	Correct	20 ms	604 KB	Output is correct
9	Correct	30 ms	648 KB	Output is correct
10	Correct	30 ms	860 KB	Output is correct
11	Correct	33 ms	768 KB	Output is correct
12	Correct	28 ms	852 KB	Output is correct
13	Correct	34 ms	852 KB	Output is correct
14	Correct	34 ms	852 KB	Output is correct
15	Correct	26 ms	860 KB	Output is correct
16	Correct	28 ms	860 KB	Output is correct
17	Correct	28 ms	848 KB	Output is correct
18	Correct	23 ms	868 KB	Output is correct
19	Correct	26 ms	860 KB	Output is correct
20	Correct	27 ms	860 KB	Output is correct