Submission #602698

#	Time	Username	Problem	Language	Result	Execution time	Memory
602698		Abdulmohsen1284	Event Hopping (BOI22_events)	C++14	0 / 100	505 ms	56940 KiB

events

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

long long bg[300005],en[300005],pa[100005][35],ope=0,twos[40],inf=1e5+1;

long long fin(long long cur,long long lim)
{
	for(int i=32;i>=0;i--)
	{
		//cout<<ope<<" ";
		if(en[pa[cur][i]]<=en[lim]&&lim!=pa[cur][i])
		{
			if(pa[cur][i]!=cur)
			ope+=twos[i];
			cur=pa[cur][i];
		}
		//cout<<cur<<" ";
	}
	return cur;
}

int main()
{
	twos[0]=1;
	for(int i=1;i<34;i++)
		twos[i]=twos[i-1]*2;
	long long n,q;
	bg[inf]=2e9;
	en[inf]=2e9;

	pa[inf][0]=inf;
	cin>>n>>q;
	set <pair <pair <long long, bool> , long long > > h;
	set <pair <long long, long long > > cur;
	cur.insert({3e9,inf});
	set <long long> bef[100005];
	bef[inf].insert(3e9);
	for(int i=0;i<n;i++)
	{
		bef[i].insert(3e9);
		pa[i][0]=inf;
		cin>>bg[i]>>en[i];
		h.insert({{bg[i],false},i});
		h.insert({{en[i],true},i});
	}
	vector < pair <long long,long long > > rem;
	long long def=-2e9;
	for(auto i: h)
	{
		if(i.first.first!=def)
		{
			for(auto hg : rem)
			{
				cur.erase({hg.first,hg.second});
			}
			rem.clear();
		}
		if(i.first.second)
		{	
			rem.push_back({i.first.first*-1,i.second});
			//cout<<cur.size()<<" ";
			auto fg = *cur.begin();
			if(en[fg.second]!=en[i.second])
			pa[i.second][0]=fg.second;
			bef[fg.second].insert(bg[i.second]);
		}
		else
		{
			cur.insert({en[i.second]*-1,i.second});
		}
		def=i.first.first;
	}
	for(int i=1;i<33;i++)
	{
		for(int j=0;j<n;j++)
		{
			pa[j][i]=pa[pa[j][i-1]][i-1];
			//cout<<pa[j][i]<<" ";
		}
	}
	for(int i=0;i<q;i++)
	{
		long long fr,sc;
		ope=1;
		cin>>fr>>sc;
		fr--;
		sc--;
		if(fr==sc){
			cout<<"0\n";
			continue;
		}
		long long las=fin(fr,sc);
		//cout<<*bef[sc].begin()<<" "<<en[las]<<" ";
		if(*bef[sc].begin()<=en[las]&&en[sc]>=en[fr]&&las!=inf)
		{
			cout<<ope<<"\n";
		}
		else{
			cout<<"impossible\n";
		}
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30