oj.uz

Submission #954443

# Submission time Handle Problem Language Result Execution time Memory
954443 2024-03-27T23:07:09 Z TAhmed33 Event Hopping (BOI22_events) C++
25 / 100
 1500 ms 7508 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
const int B = 18;
int dp[B][MAXN];
int n, q;
pair <int, int> a[MAXN];
int jump (int a, int b) {
	for (int i = B - 1; i >= 0; i--) {
		if (b & (1 << i)) {
			a = dp[i][a];
		}
	}
	return a;
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	for (int i = 1; i <= n; i++) {
		dp[0][i] = i;
		for (int j = 1; j <= n; j++) {
			if (a[j].second >= a[i].first && a[j].second <= a[i].second) {
				if (a[j].first < a[dp[0][i]].first) dp[0][i] = j;
			}
		}
	}
	for (int i = 1; i < B; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
	while (q--) {
		int x, y; cin >> x >> y;
		if (x == y) {
			cout << "0\n";
			continue;
		}
		int ans = 0;
		if (a[y].first <= a[x].second) {
			ans = -1;
		} else {
			auto l = y;
			for (int i = B - 1; i >= 0; i--) {
				auto g = dp[i][l];
				if (!g) continue;
				if (a[g].first > a[x].second) {
					ans ^= 1 << i;
					l = g;
				}
			}
		}
		y = jump(y, ans + 1);
		if (a[x].second <= a[y].second && a[x].second >= a[y].first) {
			cout << ans + 2 << '\n';
		} else {
			cout << "impossible\n";
		}
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 5 ms 6492 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 5 ms 6488 KB Output is correct
6 Correct 4 ms 6492 KB Output is correct
7 Correct 5 ms 6492 KB Output is correct
8 Correct 4 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 5 ms 6492 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 5 ms 6488 KB Output is correct
6 Correct 4 ms 6492 KB Output is correct
7 Correct 5 ms 6492 KB Output is correct
8 Correct 4 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 4 ms 6492 KB Output is correct
13 Correct 4 ms 6492 KB Output is correct
14 Correct 4 ms 6492 KB Output is correct
15 Correct 4 ms 6492 KB Output is correct
16 Correct 5 ms 6492 KB Output is correct
17 Correct 4 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 138 ms 7228 KB Output is correct
20 Correct 95 ms 7152 KB Output is correct
21 Correct 99 ms 7408 KB Output is correct
22 Correct 100 ms 7508 KB Output is correct
23 Correct 108 ms 7400 KB Output is correct
24 Correct 89 ms 7232 KB Output is correct
25 Correct 97 ms 6992 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 5 ms 6492 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 5 ms 6488 KB Output is correct
6 Correct 4 ms 6492 KB Output is correct
7 Correct 5 ms 6492 KB Output is correct
8 Correct 4 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 4 ms 6492 KB Output is correct
13 Correct 4 ms 6492 KB Output is correct
14 Correct 4 ms 6492 KB Output is correct
15 Correct 4 ms 6492 KB Output is correct
16 Correct 5 ms 6492 KB Output is correct
17 Correct 4 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Execution timed out 1576 ms 2652 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 1516 ms 2904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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