Submission #1216598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216598		MuhammadSaram	Event Hopping (BOI22_events)	C++20	100 / 100	521 ms	54836 KiB

events

/********************* بسم الله الرحمن الرحيم ***********************/
 /******************** ٱلْحَمْدُ لِلَّٰهِ رَبِّ ٱلْعَالَمِينَ *************************/
/******************* Prophet Muhammad صلى الله عليه وسلم ************/
   /*********************** وَقُل رَّبِّ زِدْنِي عِلْمًا **************************/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

const int M = 1e5 + 1, lg = 17, inf = 1e9+5;

pair<int,int> seg[M*2];
int par[M][lg];
set<pair<int,int>> ms[M];

void modify(int p,int v=0,int s=1,int e=M+1)
{
	if (s+1==e)
	{
		seg[v]=*ms[p].begin();
		return;
	}
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	if (p<mid)
		modify(p,lc,s,mid);
	else
		modify(p,rc,mid,e);
	seg[v]=min(seg[lc],seg[rc]);
}

pair<int,int> get(int l,int r,int v=0,int s=1,int e=M+1)
{
	if (l>=e or r<=s)
		return {inf,0};
	if (l<=s && e<=r)
		return seg[v];
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	return min(get(l,r,rc,mid,e),get(l,r,lc,s,mid));
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	for (int i=0;i<M*2;i++) seg[i]={inf,0},ms[i/2].insert({inf,0});
	
	int n,q;
	cin>>n>>q;
	int s[n+1]={},e[n+1];
	map<int,vector<int>,greater<int>> mp;
	set<int> se;
	for (int i=1;i<=n;i++)
	{
		cin>>s[i]>>e[i];
		mp[s[i]].push_back(i);
		mp[e[i]].push_back(i);
		se.insert(e[i]);
	}
	map<int,int> ind;
	for (int i:se)
		ind[i]=ind.size();
	se.clear();
	for (auto [x,v]:mp)
	{
		for (auto i:v)
			if (!se.count(i))
				ms[ind[e[i]]].insert({s[i],i}),modify(ind[e[i]]);
		for (auto i:v)
			if (se.count(i))
			{
				pair<int,int> p=get(1,ind[e[i]]+1);
				if (p.first<s[i])
					par[i][0]=p.second;
			}
		for (auto i:v)
			if (se.count(i))
				ms[ind[e[i]]].erase({s[i],i}),modify(ind[e[i]]),se.erase(i);
			else
				se.insert(i);
	}
	for (int p=1;p<lg;p++)
		for (int i=1;i<=n;i++)
			par[i][p]=par[par[i][p-1]][p-1];
	while (q--)
	{
		int x,y;
		cin>>x>>y;
		if (x==y)
			cout<<0<<endl;
		else if(s[y]<=e[x] && e[x]<=e[y])
			cout<<1<<endl;
		else if(e[x]>e[y])
			cout<<"impossible"<<endl;
		else
		{
			int ans=2,dm=y;
			for (int p=lg-1;p>=0;p--)
				if (s[par[dm][p]]>e[x])
					dm=par[dm][p],ans+=(1<<p);
			if (par[dm][0])
				cout<<ans<<endl;
			else
				cout<<"impossible"<<endl;
		}
	}
	
	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