Submission #1150415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150415		vako_p	Event Hopping (BOI22_events)	C++20	100 / 100	85 ms	21948 KiB

events

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e6 + 5;
ll n,q,p[mxN][20],idx[mxN];
pair<ll,pair<ll,ll>> a[mxN];	
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> a[i].second.first >> a[i].first;
		a[i].second.second = i;
	}	
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; i++){
		idx[a[i].second.second] = i;
	}
	vector<pair<ll,ll>> st;
	for(int i = 1; i <= n; i++){
		auto it = lower_bound(st.begin(), st.end(), make_pair(a[i].second.first, 0LL));
		if(it == st.end()){
			for(int j = 0; j < 20; j++) p[i][j] = i;
		}
		else{
			p[i][0] = (*it).second;
			for(int j = 1; j < 20; j++) p[i][j] = p[p[i][j - 1]][j - 1];
		}
		while(!st.empty()){
			if(a[st[st.size() - 1].second].second.first >= a[i].second.first)
				st.pop_back();
			else break;
		}
		st.pb({a[i].first, i});
	}
	while(q--){
		ll x,y;
		cin >> x >> y;
		x = idx[x];
		y = idx[y];
		if(x == y){
			cout << 0 << '\n';
			continue;
		}
		if(a[y].first < a[x].first){
			cout << "impossible" << '\n';
			continue;
		}
		if(a[y].second.first <= a[x].first){
			cout << 1 << '\n';
			continue;
		}
		ll ans = 2;
		for(int i = 19; i >= 0; i--){
			if(a[p[y][i]].second.first > a[x].first){
				y = p[y][i];
				ans += (1LL << i);
			}
		}
		y = p[y][0];
		if(a[y].second.first > a[x].first){
			cout << "impossible" << '\n';
			continue;
		}
		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