Submission #601115

#	Time	Username	Problem	Language	Result	Execution time	Memory
601115		CSQ31	Event Hopping (BOI22_events)	C++17	100 / 100	170 ms	19280 KiB

events

#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
const int MAXN = 1e5+1;
int s[MAXN],e[MAXN];
//fuck binlift how
//p(k,i) = min s if we jump backwards 2^k times
//p(k-1,i) = min of p(k-1),i<= x <= i ,p(k-1,x)
//yeesh but this n log^2n
//should pass maybe?
//1e5 * 18 * 18 = 3e7
int p[19][MAXN];
typedef pair<int,int> pii;
#define fi first
#define se second
pii T[8*MAXN];
pii mn[2*MAXN];
void build(int v,int l,int r){
	if(l==r){
		T[v] = mn[l];
		return;
	}
	int tm = (l+r)/2;
	build(2*v,l,tm);
	build(2*v+1,tm+1,r);
	T[v] = min(T[2*v],T[2*v+1]);
	
}
pii query(int v,int l,int r,int tl,int tr){
	if(l>r)return {1e9,-1};
	if(l==tl && r==tr)return T[v];
	int tm = (tl+tr)/2;
	return min(query(2*v,l,min(r,tm),tl,tm),
	           query(2*v+1,max(l,tm+1),r,tm+1,tr));
}
int main()
{
	owo
	int n,q;
	cin>>n>>q;
	vector<int>crd;
	for(int i=0;i<n;i++)cin>>s[i]>>e[i];
	for(int i=0;i<n;i++){
		crd.push_back(s[i]);
		crd.push_back(e[i]);
	}
	sort(all(crd));
	crd.resize(unique(all(crd)) - crd.begin());
	for(int i=0;i<n;i++){
		s[i] = lower_bound(all(crd),s[i]) - crd.begin()+1;
		e[i] = lower_bound(all(crd),e[i]) - crd.begin()+1;
	}
	int m = crd.size();
	for(int i=1;i<=m;i++)mn[i] = {i,-1};
	for(int i=0;i<n;i++)mn[e[i]] = min(mn[e[i]],{s[i],i});
	build(1,1,m);
	for(int i=0;i<n;i++){
		p[0][i] = i;
		pii res = query(1,s[i],e[i],1,m);
		if(res.se != -1)p[0][i] = res.se;	
		
	}
	for(int i=1;i<=18;i++){
		for(int j=0;j<n;j++){
			p[i][j] = p[i-1][p[i-1][j]];	
		}
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		l--;
		r--;
		if(l==r){
			cout<<0<<'\n';
			continue;
		}
		if(e[l] > e[r]){
			cout<<"impossible"<<'\n';
			continue;
		}
		if(s[r] <= e[l]){
			cout<<1<<'\n';
			continue;
		}
		int ans = 1; //one for actually arrivinf at l
		/*
		while(s[r] > e[l]){
			if(p[0][r] == r){
				ans = -1;
				break;
			}
			ans++;
			r = p[0][r];
		}*/
		for(int i=18;i>=0;i--){
			int v = p[i][r];
			if(s[v] > e[l]){
				r = v;
				ans+=(1<<i);
			}
		}
		ans++;
		if(r == p[0][r])ans=-1;	
		if(ans==-1)cout<<"impossible"<<'\n';
		else cout<<ans<<'\n';
	}
	
	
}

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