Submission #896408

#	Time	Username	Problem	Language	Result	Execution time	Memory
896408		Abdalaziz_Alshami	Event Hopping (BOI22_events)	C++17	0 / 100	1591 ms	15536 KiB

events

#include<iostream>
#include<set>
#include<map>
#include<utility>
#define st first
#define ed second
//#define int int64_t
#define endl '\n'
using namespace std;
signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,q; cin>>n>>q;
	pair<int,int>a[n+1];
	map<int,int>pres;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].st>>a[i].ed;
		pres[a[i].st]; pres[a[i].ed];
	}
	int d=1;
	for(auto &e:pres) e.ed=d,d++;
	set<int> m[d+10];
	for(int i=1; i<=n;i++) 
	{
		a[i].st=pres[a[i].st];
		a[i].ed=pres[a[i].ed];
		m[a[i].st].insert(-a[i].ed);
	}
	while(q--)
	{
		int u,v; cin>>u>>v; 
		if(u==v) {  cout<<0<<endl; continue;}
		int i=a[u].st,mx=a[u].ed,g1=a[v].st,g2=a[v].ed,p=-1,ans=0;
		bool f=false;
		while(i<=mx)
		{
			auto it=m[i].lower_bound(-g2);
			if(it!=m[i].end()) p=max(p,-*it);
			if(i==mx){
				 mx=p; ans++;
				 if(mx==g2&&i>=g1) { f=true; break;}
			}
			i++;
		}
		if(f) cout<<ans<<endl;
		else  cout<<"impossible"<<endl;
	}
}

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