Submission #574313

#	Time	Username	Problem	Language	Result	Execution time	Memory
574313		Jasiekstrz	Event Hopping (BOI22_events)	C++17	100 / 100	395 ms	23260 KiB

events

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
const int P=1<<18;
const int L=18;
const int INF=1e9+7;
pair<int,int> t[N+10];
map<int,int> sc;
int pot;
pair<int,int> tr[2*P+10];
int jmp[N+10][L+1];
bool vis_jmp[N+10];
void add(int x,pair<int,int> c)
{
	for(x+=pot-1;x>=1;x/=2)
		tr[x]=min(tr[x],c);
	return;
}
int read(int l,int r)
{
	pair<int,int> ans={INF,0};
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ans=min(ans,tr[l++]);
		if(r%2==0)
			ans=min(ans,tr[r--]);
	}
	return ans.se;
}
void calc_jmp(int x)
{
	if(t[jmp[x][0]].fi>=t[x].fi)
		jmp[x][0]=0;
	vis_jmp[x]=true;
	if(!vis_jmp[jmp[x][0]])
		calc_jmp(jmp[x][0]);
	for(int i=1;i<=L;i++)
		jmp[x][i]=jmp[jmp[x][i-1]][i-1];
	return;
}
pair<int,int> far(int x,int y)
{
	int c=0;
	for(int i=L;i>=0;i--)
	{
		if(t[jmp[x][i]].fi>y)
		{
			c+=(1<<i);
			x=jmp[x][i];
		}
	}
	return {x,c};
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i].fi>>t[i].se;
		sc[t[i].fi]=sc[t[i].se]=0;
	}
	int k=0;
	for(auto [a,b]:sc)
		sc[a]=++k;
	for(pot=1;pot<k;pot*=2);
	for(int i=1;i<=2*pot;i++)
		tr[i]={INF,0};
	for(int i=1;i<=n;i++)
		add(sc[t[i].se],{t[i].fi,i});
	for(int i=1;i<=n;i++)
		jmp[i][0]=read(sc[t[i].fi],sc[t[i].se]);
	vis_jmp[0]=true;
	for(int i=1;i<=n;i++)
	{
		if(!vis_jmp[i])
			calc_jmp(i);
		//cerr<<i<<": "<<jmp[i][0]<<"\n";
	}
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(a==b)
		{
			cout<<"0\n";
			continue;
		}
		auto [x,c]=far(b,t[a].fi);
		if(t[a].se>t[x].se)
			cout<<"impossible\n";
		else if(t[a].se>=t[x].fi)
			cout<<c+1<<"\n";
		else if(jmp[x][0]==0)
			cout<<"impossible\n";
		else
			cout<<c+2<<"\n";
	}
	return 0;
}

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