#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair <ll, ll>;
int n;
const int N = 2e5 + 5;
const int M = 20;
const int INF = 1e6;
int nums[N], L[N], R[N];
vector <int> paths[N];
bool test1;
int pos[N];
int maxi[N][M];
int nx[N][M];
int greedy[N][M];
int A, B, C, D;
// int getRight(int pos, )
int getMax(int l, int r) {
int p = 0;
while(l + (1<<(p+1)) - 1 <= r) p++;
return max(maxi[l][p], maxi[r - (1<<p) + 1][p]);
}
void init(int _n, vector<int> _nums) {
test1 = 1;
n = _n;
nums[0] = nums[n+1] = INF;
for (int i = 0; i < n; i++) test1 &= (_nums[i] == i+1);
for (int i = 1; i <= n; i++) {
maxi[i][0] = nums[i] = _nums[i-1];
pos[nums[i]] = i;
}
L[0] = R[0] = 0;
L[n+1] = R[n+1] = n+1;
stack <int> stk;
stk.push(0);
for (int i = 1; i <= n; i++) {
while(nums[stk.top()] < nums[i]) stk.pop();
L[i] = stk.top();
stk.push(i);
}
while(!stk.empty()) stk.pop();
stk.push(n+1);
for (int i = n; i > 0; i--) {
while(nums[stk.top()] < nums[i]) stk.pop();
R[i] = stk.top();
stk.push(i);
}
for (int i = 1; i <= n; i++) {
int a = L[i], b = R[i];
nx[i][0] = b;
if (nums[a] == INF) swap(a, b);
if (nums[a] == INF) greedy[i][0] = i;
if (nums[a] < nums[b] && nums[b] != INF) a = b;
greedy[i][0] = a;
}
for (int j = 1; j < M; j++)
for (int i = 1; i <= n; i++) {
maxi[i][j] = max(maxi[i][j-1], maxi[min(n, i+(1<<(j-1)))][j-1]);
nx[i][j] = nx[nx[i][j-1]][j-1];
greedy[i][j] = greedy[greedy[i][j-1]][j-1];
}
// for (int i = 1; i <= n; i++)
// for (int j = i; j <= n; j++) cout << i << ',' << j << ": " << getMax(i, j) << '\n';
}
int minimum_jumps(int _A, int _B, int _C, int _D) {
A = 1 + _A;
B = 1 + _B;
C = 1 + _C;
D = 1 + _D;
if (B+1 == C) return (nums[B] > getMax(C, D) ? -1 : 1);
int x = getMax(A, B);
int y = getMax(B+1, C-1);
int z = getMax(C, D);
if (y > z) return -1;
if (nums[B] > z) return -1;
int res = 0;
if (x < y) { // 1 2 3
int p = pos[x];
for (int i = M-1; i >= 0; i--) {
if (nums[greedy[p][i]] < y) {
res += (1<<i);
p = greedy[p][i];
}
}
if (y <= nums[greedy[p][0]] && nums[greedy[p][0]] <= z) return res + 2;
for (int i = M-1; i >= 0; i--) {
if (nums[nx[p][i]] <= y) {
res += (1<<i);
p = nx[p][i];
}
}
return res+1;
} else if (x < z) { // 2 1 3
return 1;
} else if (x > z) { // 3 1 2
int l = A, r = B, p = r;
while (l <= r) {
int mid = (l+r)>>1;
int tmp = getMax(mid, B);
if (tmp > y && tmp < z) return 1;
if (tmp > z) {
l = mid+1;
} else {
p = min(p, mid);
r = mid-1;
}
}
for (int i = M-1; i >= 0; i--) {
if (nums[nx[p][i]] <= y) {
res += (1<<i);
p = nx[p][i];
}
}
return res + 1;
}
}
Compilation message
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:118:1: warning: control reaches end of non-void function [-Wreturn-type]
118 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
4944 KB |
Output is correct |
3 |
Correct |
210 ms |
46792 KB |
Output is correct |
4 |
Correct |
927 ms |
57464 KB |
Output is correct |
5 |
Correct |
938 ms |
31388 KB |
Output is correct |
6 |
Correct |
1057 ms |
57484 KB |
Output is correct |
7 |
Correct |
833 ms |
40884 KB |
Output is correct |
8 |
Correct |
1079 ms |
57392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5072 KB |
Output is correct |
2 |
Correct |
4 ms |
4984 KB |
Output is correct |
3 |
Correct |
3 ms |
4944 KB |
Output is correct |
4 |
Correct |
2 ms |
4944 KB |
Output is correct |
5 |
Correct |
5 ms |
4944 KB |
Output is correct |
6 |
Incorrect |
5 ms |
5072 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5072 KB |
Output is correct |
2 |
Correct |
4 ms |
4984 KB |
Output is correct |
3 |
Correct |
3 ms |
4944 KB |
Output is correct |
4 |
Correct |
2 ms |
4944 KB |
Output is correct |
5 |
Correct |
5 ms |
4944 KB |
Output is correct |
6 |
Incorrect |
5 ms |
5072 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
4944 KB |
Output is correct |
3 |
Correct |
2 ms |
4944 KB |
Output is correct |
4 |
Correct |
2 ms |
4944 KB |
Output is correct |
5 |
Correct |
107 ms |
46584 KB |
Output is correct |
6 |
Correct |
112 ms |
56704 KB |
Output is correct |
7 |
Correct |
69 ms |
31432 KB |
Output is correct |
8 |
Correct |
131 ms |
56520 KB |
Output is correct |
9 |
Correct |
15 ms |
12752 KB |
Output is correct |
10 |
Correct |
126 ms |
56648 KB |
Output is correct |
11 |
Correct |
132 ms |
57432 KB |
Output is correct |
12 |
Incorrect |
129 ms |
57220 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
3 ms |
4944 KB |
Output is correct |
4 |
Correct |
215 ms |
28592 KB |
Output is correct |
5 |
Correct |
886 ms |
56704 KB |
Output is correct |
6 |
Correct |
471 ms |
13520 KB |
Output is correct |
7 |
Correct |
974 ms |
56652 KB |
Output is correct |
8 |
Correct |
488 ms |
22728 KB |
Output is correct |
9 |
Correct |
1020 ms |
56660 KB |
Output is correct |
10 |
Correct |
1228 ms |
57480 KB |
Output is correct |
11 |
Correct |
1096 ms |
57344 KB |
Output is correct |
12 |
Correct |
976 ms |
57360 KB |
Output is correct |
13 |
Correct |
1109 ms |
56544 KB |
Output is correct |
14 |
Correct |
797 ms |
56932 KB |
Output is correct |
15 |
Correct |
892 ms |
57484 KB |
Output is correct |
16 |
Correct |
904 ms |
57476 KB |
Output is correct |
17 |
Correct |
4 ms |
4944 KB |
Output is correct |
18 |
Correct |
3 ms |
4944 KB |
Output is correct |
19 |
Correct |
4 ms |
4944 KB |
Output is correct |
20 |
Correct |
5 ms |
5072 KB |
Output is correct |
21 |
Correct |
5 ms |
5072 KB |
Output is correct |
22 |
Correct |
5 ms |
5072 KB |
Output is correct |
23 |
Correct |
5 ms |
5072 KB |
Output is correct |
24 |
Correct |
4 ms |
5072 KB |
Output is correct |
25 |
Correct |
3 ms |
5072 KB |
Output is correct |
26 |
Correct |
3 ms |
5200 KB |
Output is correct |
27 |
Correct |
21 ms |
5456 KB |
Output is correct |
28 |
Correct |
21 ms |
5456 KB |
Output is correct |
29 |
Correct |
27 ms |
5456 KB |
Output is correct |
30 |
Correct |
20 ms |
5456 KB |
Output is correct |
31 |
Correct |
22 ms |
5456 KB |
Output is correct |
32 |
Correct |
3 ms |
4944 KB |
Output is correct |
33 |
Correct |
65 ms |
34848 KB |
Output is correct |
34 |
Correct |
117 ms |
56648 KB |
Output is correct |
35 |
Correct |
113 ms |
57348 KB |
Output is correct |
36 |
Correct |
129 ms |
56600 KB |
Output is correct |
37 |
Correct |
144 ms |
56912 KB |
Output is correct |
38 |
Correct |
119 ms |
57496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
3 ms |
4944 KB |
Output is correct |
4 |
Correct |
215 ms |
28592 KB |
Output is correct |
5 |
Correct |
886 ms |
56704 KB |
Output is correct |
6 |
Correct |
471 ms |
13520 KB |
Output is correct |
7 |
Correct |
974 ms |
56652 KB |
Output is correct |
8 |
Correct |
488 ms |
22728 KB |
Output is correct |
9 |
Correct |
1020 ms |
56660 KB |
Output is correct |
10 |
Correct |
1228 ms |
57480 KB |
Output is correct |
11 |
Correct |
1096 ms |
57344 KB |
Output is correct |
12 |
Correct |
976 ms |
57360 KB |
Output is correct |
13 |
Correct |
1109 ms |
56544 KB |
Output is correct |
14 |
Correct |
797 ms |
56932 KB |
Output is correct |
15 |
Correct |
892 ms |
57484 KB |
Output is correct |
16 |
Correct |
904 ms |
57476 KB |
Output is correct |
17 |
Correct |
4 ms |
4944 KB |
Output is correct |
18 |
Correct |
3 ms |
4944 KB |
Output is correct |
19 |
Correct |
4 ms |
4944 KB |
Output is correct |
20 |
Correct |
5 ms |
5072 KB |
Output is correct |
21 |
Correct |
5 ms |
5072 KB |
Output is correct |
22 |
Correct |
5 ms |
5072 KB |
Output is correct |
23 |
Correct |
5 ms |
5072 KB |
Output is correct |
24 |
Correct |
4 ms |
5072 KB |
Output is correct |
25 |
Correct |
3 ms |
5072 KB |
Output is correct |
26 |
Correct |
3 ms |
5200 KB |
Output is correct |
27 |
Correct |
21 ms |
5456 KB |
Output is correct |
28 |
Correct |
21 ms |
5456 KB |
Output is correct |
29 |
Correct |
27 ms |
5456 KB |
Output is correct |
30 |
Correct |
20 ms |
5456 KB |
Output is correct |
31 |
Correct |
22 ms |
5456 KB |
Output is correct |
32 |
Correct |
3 ms |
4944 KB |
Output is correct |
33 |
Correct |
65 ms |
34848 KB |
Output is correct |
34 |
Correct |
117 ms |
56648 KB |
Output is correct |
35 |
Correct |
113 ms |
57348 KB |
Output is correct |
36 |
Correct |
129 ms |
56600 KB |
Output is correct |
37 |
Correct |
144 ms |
56912 KB |
Output is correct |
38 |
Correct |
119 ms |
57496 KB |
Output is correct |
39 |
Correct |
3 ms |
4944 KB |
Output is correct |
40 |
Correct |
4 ms |
4944 KB |
Output is correct |
41 |
Correct |
3 ms |
4944 KB |
Output is correct |
42 |
Correct |
200 ms |
28536 KB |
Output is correct |
43 |
Correct |
846 ms |
56648 KB |
Output is correct |
44 |
Correct |
551 ms |
13440 KB |
Output is correct |
45 |
Correct |
837 ms |
56520 KB |
Output is correct |
46 |
Correct |
498 ms |
22728 KB |
Output is correct |
47 |
Correct |
744 ms |
56656 KB |
Output is correct |
48 |
Correct |
763 ms |
57476 KB |
Output is correct |
49 |
Correct |
1149 ms |
57336 KB |
Output is correct |
50 |
Correct |
1114 ms |
57380 KB |
Output is correct |
51 |
Correct |
788 ms |
56580 KB |
Output is correct |
52 |
Correct |
871 ms |
57164 KB |
Output is correct |
53 |
Correct |
854 ms |
57476 KB |
Output is correct |
54 |
Correct |
858 ms |
57476 KB |
Output is correct |
55 |
Correct |
3 ms |
4944 KB |
Output is correct |
56 |
Incorrect |
162 ms |
56464 KB |
Output isn't correct |
57 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
4944 KB |
Output is correct |
3 |
Correct |
210 ms |
46792 KB |
Output is correct |
4 |
Correct |
927 ms |
57464 KB |
Output is correct |
5 |
Correct |
938 ms |
31388 KB |
Output is correct |
6 |
Correct |
1057 ms |
57484 KB |
Output is correct |
7 |
Correct |
833 ms |
40884 KB |
Output is correct |
8 |
Correct |
1079 ms |
57392 KB |
Output is correct |
9 |
Correct |
3 ms |
5072 KB |
Output is correct |
10 |
Correct |
4 ms |
4984 KB |
Output is correct |
11 |
Correct |
3 ms |
4944 KB |
Output is correct |
12 |
Correct |
2 ms |
4944 KB |
Output is correct |
13 |
Correct |
5 ms |
4944 KB |
Output is correct |
14 |
Incorrect |
5 ms |
5072 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |