Submission #828946

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
828946	2023-08-17T21:25:10 Z	QwertyPi	Event Hopping (BOI22_events)	C++14	10 / 100	1500 ms	4124 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Execution timed out	1569 ms	4100 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	61 ms	340 KB	Output is correct
4	Correct	8 ms	340 KB	Output is correct
5	Correct	8 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	61 ms	340 KB	Output is correct
4	Correct	8 ms	340 KB	Output is correct
5	Correct	8 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	63 ms	340 KB	Output is correct
13	Correct	6 ms	340 KB	Output is correct
14	Correct	10 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Execution timed out	1580 ms	516 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	61 ms	340 KB	Output is correct
4	Correct	8 ms	340 KB	Output is correct
5	Correct	8 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	61 ms	240 KB	Output is correct
13	Correct	6 ms	340 KB	Output is correct
14	Correct	8 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Execution timed out	1577 ms	4108 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1578 ms	4124 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Execution timed out	1569 ms	4100 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-