Submission #1146810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146810		Rawlat_vanak	Event Hopping (BOI22_events)	C++20	0 / 100	1597 ms	13760 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]=max(seg[2*v],seg[2*v+1]);
	}

}
/*
void build(int v, int tl, int tr) {
	cout<<v<<'\n';
    if (tl == tr) {
        seg[v] = idk[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        seg[v] = max(seg[v*2],seg[v*2+1]);
    }
}*/



pii get(int v, int l, int r, int cl, int cr){
	if(cl>cr){
		return {0,-1};
	}
	if(l==cl and r==cr){
		return seg[v];
	}else{
		int m=(l+r)/2;
		return max(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]={s[i],i};
		}
		sort(start.begin(),start.end());
		vector<int> best(n),bruh(n),pos(n);
		idk.resize(n+1);
		for(int i=0;i<n;i++){
			idk[i+1].f=e[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,1,3).f<<' '<<get(1,1,n,1,3).s<<'\n';
		
		for(int i=0;i<n;i++){
			int l=s[i],r=e[i];
			int idx=upper_bound(bruh.begin(),bruh.end(),r)-bruh.begin();
			idx--;
			//cout<<idx<<'\n';
			if(idx==-1){
				best[i]=-1;
			}else{
				//pii tmp=max(get(1,1,n,1,pos[i]),get(1,1,n,pos[i]+2,idx+1));
				pii tmp=get(1,1,n,1,idx+1);
				if(tmp.f>=e[i]){
					best[i]=tmp.s;
				}else{
					best[i]=-1;
				}
				if(best[i]==i){
					best[i]=-1;
				}

			}

		}
		/*for(int i:best){
			cout<<i<<' ';
		}
		cout<<'\n';*/

			

		while(q--){
			int x,y;
			cin>>x>>y;
			x--;y--;
			if(x==y){
				cout<<0<<'\n';
				continue;
			}
			int cl=s[x],cr=e[x];
			int el=s[y],er=e[y];

			int ans=0;
			bool flag=true;
			if(er<cr) flag=false;
			//cout<<"hi "<<cl<<' '<<cr<<' '<<el<<' '<<er<<'\n';
			while(el>cr){
				ans++;
				if(er<cr) flag=false;
				if(best[x]==-1){
					flag=false;
					break;
				}
				x=best[x];
				cl=s[x];
				cr=e[x];
				
			}
			if(er<cr) flag=false;
			if(flag){
				cout<<ans+1<<'\n';
			}else{
				cout<<"impossible\n";
			}

		}
		
		




		



		
		



		



	
	
	


		

		

	}
	return 0;
}

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