#include "jumps.h"
#include <vector>
using namespace std;
const int N = 200000;
typedef vector<int> vi;
int max(int a, int b) { return a > b ? a : b; }
int ll[N], rr[N], qu[N], n, special;
void init(int n_, vi hh) {
int i, cnt;
special = 1;
for (i = 0; i < n; i++)
if (hh[i] != i + 1) {
special = 0;
break;
}
n = n_;
cnt = 0;
for (i = 0; i < n; i++) {
while (cnt && hh[qu[cnt - 1]] < hh[i])
cnt--;
ll[i] = cnt == 0 ? -1 : qu[cnt - 1];
qu[cnt++] = i;
}
cnt = 0;
for (i = n - 1; i >= 0; i--) {
while (cnt && hh[qu[cnt - 1]] < hh[i])
cnt--;
rr[i] = cnt == 0 ? -1 : qu[cnt - 1];
qu[cnt++] = i;
}
}
int dd[N];
int minimum_jumps(int i1, int j1, int i2, int j2) {
if (special)
return i2 - j1;
else {
int head, cnt, i;
for (i = 0; i < n; i++)
dd[i] = n;
head = cnt = 0;
for (i = i1; i <= j1; i++)
dd[i] = 0, qu[head + cnt++] = i;
while (cnt) {
int d;
i = qu[cnt--, head++], d = dd[i] + 1;
if (i2 <= i && i <= j2)
return dd[i];
if (ll[i] != -1 && dd[ll[i]] > d)
dd[ll[i]] = d, qu[head + cnt++] = ll[i];
if (rr[i] != -1 && dd[rr[i]] > d)
dd[rr[i]] = d, qu[head + cnt++] = rr[i];
}
return -1;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
200 KB |
Output is correct |
2 |
Correct |
0 ms |
200 KB |
Output is correct |
3 |
Correct |
120 ms |
3328 KB |
Output is correct |
4 |
Correct |
1053 ms |
4160 KB |
Output is correct |
5 |
Correct |
900 ms |
2192 KB |
Output is correct |
6 |
Correct |
1111 ms |
4132 KB |
Output is correct |
7 |
Correct |
775 ms |
2880 KB |
Output is correct |
8 |
Correct |
865 ms |
4104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
200 KB |
Output is correct |
2 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
200 KB |
Output is correct |
2 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
200 KB |
Output is correct |
2 |
Correct |
0 ms |
200 KB |
Output is correct |
3 |
Correct |
120 ms |
3328 KB |
Output is correct |
4 |
Correct |
1053 ms |
4160 KB |
Output is correct |
5 |
Correct |
900 ms |
2192 KB |
Output is correct |
6 |
Correct |
1111 ms |
4132 KB |
Output is correct |
7 |
Correct |
775 ms |
2880 KB |
Output is correct |
8 |
Correct |
865 ms |
4104 KB |
Output is correct |
9 |
Incorrect |
0 ms |
200 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |