Submission #959643

#	Time	Username	Problem	Language	Result	Execution time	Memory
959643		maxFedorchuk	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	34 ms	868 KiB

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 / 100