Submission #828939

#	Time	Username	Problem	Language	Result	Execution time	Memory
828939		QwertyPi	Event Hopping (BOI22_events)	C++14	10 / 100	1585 ms	3992 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;
};

event a[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};
	}
	for(int i = 0; i < q; i++){
		int u, v; cin >> u >> 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 <= n; j++){
				if(a[far].e <= a[j].e && a[j].e <= a[v].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: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30