Submission #828943

#	Time	Username	Problem	Language	Result	Execution time	Memory
828943		QwertyPi	Event Hopping (BOI22_events)	C++14	0 / 100	1572 ms	8268 KiB

events

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

const int N = 1e5 + 11;
struct event{
	int s, e, i;
};

event a[N];
int p[N], R[N];
int32_t main(){
	int n, q; cin >> n >> q;
	for(int i = 1; i <= n; i++){
		int s, e; cin >> s >> e; a[i] = {s, e, i};
	}
	sort(a + 1, a + n + 1, [](event u, event v){ return u.e <= v.e; });
	R[n] = n; for(int i = n - 1; i >= 1; i--) R[i] = a[i].e == a[i + 1].e ? R[i + 1] : i;
	for(int i = 1; i <= n; i++) p[a[i].i] = i;
	for(int i = 0; i < q; i++){
		int u, v; cin >> u >> v; u = p[u], v = p[v];
		if(a[u].e > a[v].e){
			cout << "impossible" << endl;
			continue;
		}
		if(u == v){
			cout << 0 << endl;
			continue;
		}
		int ans = 0;
		while(a[u].e < a[v].s){
			int far = u;
			for(int j = 1; j <= R[v]; j++){
				if(a[far].e <= a[j].e && a[j].s <= a[u].e){
					far = j;
				}
			}
			if(a[far].e == a[u].e){
				ans = -1;
				break;
			}else{
				u = far;
				ans++;
			}
		}
		cout << (ans == -1 ? "impossible" : to_string(ans + 1)) << endl;
	}
}

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