Submission #1146995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146995		Rawlat_vanak	Event Hopping (BOI22_events)	C++20	100 / 100	137 ms	34436 KiB

events

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define mod 1000000007
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back

vector<pii> seg,idk;

void build(int v, int l, int r){
	//cout<<v<<'\n';
	if(l>r) return;
	if(l==r){
		seg[v]=idk[l];
	}else{
		int m=(l+r)/2;
		build(2*v,l,m);
		build(2*v+1,m+1,r);
		seg[v]=min(seg[2*v],seg[2*v+1]);
	}

}




pii get(int v, int l, int r, int cl, int cr){
	if(cl>cr){
		return {1e18,-1};
	}
	if(l==cl and r==cr){
		return seg[v];
	}else{
		int m=(l+r)/2;
		return min(get(2*v,l,m,cl,min(cr,m)),get(2*v+1,m+1,r,max(m+1,cl),cr));
	}
}



int32_t main(){
	speedIO;
	int t,n,m,k,q;
	//cin>>t;
	t=1;
	while(t--){
		cin>>n>>q;
		int s[n],e[n];
		vector<pii> start(n);
		for(int i=0;i<n;i++){
			cin>>s[i]>>e[i];
			start[i]={e[i],i};
		}

		sort(start.begin(),start.end());
		vector<int> best(n),bruh(n),pos(n);
		vector<vector<int>> up(n+1,vector<int>(21));
		idk.resize(n+1);
		for(int i=0;i<n;i++){
			idk[i+1].f=s[start[i].s];
			idk[i+1].s=start[i].s;
			pos[start[i].s]=i;
			bruh[i]=start[i].f;
			//cout<<idk[i+1].f<<' '<<idk[i+1].s<<'\n';
		}
		//cout<<'\n';
		seg.resize(4*n+5,{0,-1});
		build(1,1,n);
		//cout<<get(1,1,n,6,7).f<<' '<<get(1,1,n,1,2).s<<'\n';
		
		for(int i=0;i<n;i++){
			int l=s[i],r=e[i];
			int idx1=upper_bound(bruh.begin(),bruh.end(),r)-bruh.begin()-1;
			int idx2=lower_bound(bruh.begin(),bruh.end(),l)-bruh.begin();
			pii tmp=get(1,1,n,idx2+1,idx1+1);
			best[i]=tmp.s;
			up[i][0]=best[i];
			if(best[i]==i){
				best[i]=-1;
				//up[i][0]=n;
			}

		}
		up[n][0]=n;
		/*for(int i:best){
			cout<<i<<' ';
		}
		cout<<'\n';*/

		for(int j=1;j<21;j++){
			for(int i=0;i<=n;i++){
				up[i][j]=up[up[i][j-1]][j-1];
			}
		}

		
		while(q--){
			int x,y;
			cin>>x>>y;
			x--;y--;
			int ans=0;
			bool flag=true;
			//cout<<s[x]<<' '<<e[x]<<'\n';
			if(x==y){
				cout<<0<<'\n';
				continue;
			}
			if(e[y]<e[x]){
				cout<<"impossible\n";

				continue;
			}
			if(s[y]<=e[x]){
				if(e[y]>=e[x]){
					cout<<1<<'\n';
					continue;
				}
			}
			//cout<<y<<' '<<best[y]<<' '<<best[best[y]]<<' '<<best[best[best[y]]]<<' '<<best[best[best[best[y]]]]<<'\n';
			for(int i=0;i<21;i++){
				//cout<<up[y][i]<<' '<<s[up[y][i]]<<'\n';
			}
			//cout<<'\n';


			for(int i=20;i>=0;i--){
				if(up[y][i]==n){
					flag=false;
					break;
				}
				if(s[up[y][i]]>e[x]){
					y=up[y][i];
					//cout<<y<<' '<<i<<'\n';
					ans+=(1<<i);
				}
			}
			//cout<<'\n';
			y=best[y];
			ans++;
			//cout<<ans<<'\n';
			//cout<<y<<' '<<best[y]<<' '<<best[best[y]]<<'\n';


			/*while(s[y]>e[x]){
				ans++;
				if(best[y]==-1){
					flag=false;
					break;
				}
				y=best[y];
				//cout<<y<<' ';
			}
			cout<<y<<' '<<s[y]<<' '<<e[y]<<'\n';*/
			if(e[y]<e[x] or e[x]<s[y]){
				flag=false;
				//cout<<"opops\n";
			}
			if(flag){
				cout<<ans+1<<'\n';
			}else{
				cout<<"impossible\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