#include "jumps.h"
#include "bits/stdc++.h"
using namespace std;
const int lg = 18, N = 2e5 + 5, inf = 1e9;
vector<int> l(N), r(N);
int n;
void init(int N, vector<int> H) {
n = N;
stack<int> s;
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() and H[s.top()] < H[i]) s.pop();
r[i] = s.empty() ? n : s.top();
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = 0; i < n; i++) {
while (!s.empty() and H[s.top()] < H[i]) s.pop();
l[i] = s.empty() ? -1 : s.top();
}
}
int minimum_jumps(int a, int b, int c, int d) {
return c - b;
queue<int> q;
vector<int> ans(n, inf);
for (int i = a; i <= b; i++) ans[i] = 0, q.push(i);
while (!q.empty()) {
int x = q.front(); q.pop();
if (c <= x and x <= d) return ans[x];
if (l[x] >= 0 and ans[l[x]] > ans[x] + 1) {
ans[l[x]] = ans[x] + 1;
q.push(l[x]);
}
if (r[x] < n and ans[r[x]] > ans[x] + 1) {
ans[r[x]] = ans[x] + 1;
q.push(r[x]);
}
}
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Correct |
1 ms |
1880 KB |
Output is correct |
3 |
Correct |
61 ms |
4044 KB |
Output is correct |
4 |
Correct |
607 ms |
4324 KB |
Output is correct |
5 |
Correct |
494 ms |
3176 KB |
Output is correct |
6 |
Correct |
554 ms |
4176 KB |
Output is correct |
7 |
Correct |
460 ms |
3416 KB |
Output is correct |
8 |
Correct |
570 ms |
4328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Correct |
1 ms |
1880 KB |
Output is correct |
3 |
Correct |
61 ms |
4044 KB |
Output is correct |
4 |
Correct |
607 ms |
4324 KB |
Output is correct |
5 |
Correct |
494 ms |
3176 KB |
Output is correct |
6 |
Correct |
554 ms |
4176 KB |
Output is correct |
7 |
Correct |
460 ms |
3416 KB |
Output is correct |
8 |
Correct |
570 ms |
4328 KB |
Output is correct |
9 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |