#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int LOGMAX = 20;
constexpr int NMAX = 2e5 + 5;
int st[LOGMAX][NMAX];
int dr[LOGMAX][NMAX];
int bst[LOGMAX][NMAX];
int Lg[NMAX];
int vf;
void init(int N, std::vector<int> H) {
deque <int> D;
Lg[1] = 0;
for (int i = 2; i <= N; ++ i )
Lg[i] = Lg[i/2] + 1;
vf = Lg[N];
for (int i = 0; i <= vf; ++ i )
for (int j = 0; j < N; ++ j )
st[i][j] = dr[i][j] = bst[i][j] = -1;
for (int i = 0; i < N; ++ i ) {
while (!D.empty() && H[D.back()] < H[i]) {
dr[0][D.back()] = i;
D.pop_back();
}
if (!D.empty()) st[0][i] = D.back();
D.push_back(i);
}
for (int i = 0; i < N; ++ i ) {
bst[0][i] = -1;
if (st[0][i] == -1) bst[0][i] = dr[0][i];
else if (dr[0][i] == -1) bst[0][i] = st[0][i];
else {
bst[0][i] = (H[st[0][i]] > H[dr[0][i]] ? st[0][i] : dr[0][i]);
}
}
for (int i = 1; i <= Lg[N]; ++ i ) {
for (int j = 0; j + (1<<i) - 1 < N; ++ j ) {
if (st[i-1][j] == -1) st[i][j] = -1;
else st[i][j] = st[i-1][st[i-1][j]];
if (dr[i-1][j] == -1) dr[i][j] = -1;
else dr[i][j] = dr[i-1][dr[i-1][j]];
if (bst[i-1][j] == -1) bst[i][j] = -1;
else bst[i][j] = bst[i-1][bst[i-1][j]];
}
}
}
int Can (int pos, int C, int D) {
int ans = 0;
if (C <= pos && pos <= D) return 0;
for (int i = vf; i >= 0; -- i ) {
if (dr[i][pos] == -1) continue;
if (dr[i][pos] >= C) continue;
pos = dr[i][pos];
ans += (1<<i);
}
pos = dr[0][pos];
++ ans;
if (pos == -1) return -1;
return (pos <= D ? ans : -1);
}
int minimum_jumps(int A, int B, int C, int D) {
int best_pos_AB = B;
if (Can(B, C, D) == -1) return -1;
for (int i = vf; i >= 0; -- i ) {
if (st[i][best_pos_AB] == -1) continue;
if (st[i][best_pos_AB] < A) continue;
int new_pos = st[i][best_pos_AB];
if (Can(new_pos, C, D) >= 0) best_pos_AB = new_pos;
}
int answer = Can(best_pos_AB, C, D);
int contor = 0;
for (int i = vf; i >= 0; -- i ) {
if (bst[i][best_pos_AB] == -1) continue;
if (bst[i][best_pos_AB] >= C) continue;
int new_pos = bst[i][best_pos_AB];
int x;
if ((x = Can(new_pos, C, D)) >= 0) {
contor += (1<<i);
answer = x + contor;
best_pos_AB = bst[i][best_pos_AB];
}
}
return answer;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
178 ms |
36008 KB |
Output is correct |
4 |
Correct |
1341 ms |
44844 KB |
Output is correct |
5 |
Correct |
1068 ms |
21772 KB |
Output is correct |
6 |
Correct |
1318 ms |
44828 KB |
Output is correct |
7 |
Correct |
1096 ms |
30936 KB |
Output is correct |
8 |
Correct |
1407 ms |
44956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
2 ms |
336 KB |
Output is correct |
6 |
Incorrect |
3 ms |
464 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
2 ms |
336 KB |
Output is correct |
6 |
Incorrect |
3 ms |
464 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
45 ms |
36380 KB |
Output is correct |
6 |
Correct |
66 ms |
44828 KB |
Output is correct |
7 |
Correct |
23 ms |
22088 KB |
Output is correct |
8 |
Correct |
47 ms |
44828 KB |
Output is correct |
9 |
Correct |
6 ms |
6096 KB |
Output is correct |
10 |
Correct |
49 ms |
44872 KB |
Output is correct |
11 |
Correct |
51 ms |
44912 KB |
Output is correct |
12 |
Correct |
48 ms |
44888 KB |
Output is correct |
13 |
Correct |
42 ms |
44856 KB |
Output is correct |
14 |
Correct |
49 ms |
44876 KB |
Output is correct |
15 |
Incorrect |
44 ms |
45240 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
207 ms |
19784 KB |
Output is correct |
5 |
Correct |
672 ms |
44872 KB |
Output is correct |
6 |
Correct |
631 ms |
7080 KB |
Output is correct |
7 |
Correct |
646 ms |
44832 KB |
Output is correct |
8 |
Correct |
592 ms |
15048 KB |
Output is correct |
9 |
Correct |
930 ms |
44840 KB |
Output is correct |
10 |
Correct |
1274 ms |
44836 KB |
Output is correct |
11 |
Correct |
1142 ms |
44872 KB |
Output is correct |
12 |
Correct |
1214 ms |
44852 KB |
Output is correct |
13 |
Correct |
766 ms |
45000 KB |
Output is correct |
14 |
Correct |
1228 ms |
45244 KB |
Output is correct |
15 |
Correct |
966 ms |
45732 KB |
Output is correct |
16 |
Correct |
1096 ms |
45760 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
2 ms |
336 KB |
Output is correct |
20 |
Correct |
3 ms |
464 KB |
Output is correct |
21 |
Correct |
3 ms |
464 KB |
Output is correct |
22 |
Correct |
3 ms |
464 KB |
Output is correct |
23 |
Correct |
3 ms |
464 KB |
Output is correct |
24 |
Correct |
3 ms |
480 KB |
Output is correct |
25 |
Correct |
1 ms |
464 KB |
Output is correct |
26 |
Correct |
1 ms |
464 KB |
Output is correct |
27 |
Correct |
17 ms |
720 KB |
Output is correct |
28 |
Correct |
23 ms |
720 KB |
Output is correct |
29 |
Correct |
27 ms |
720 KB |
Output is correct |
30 |
Correct |
24 ms |
720 KB |
Output is correct |
31 |
Correct |
27 ms |
720 KB |
Output is correct |
32 |
Correct |
0 ms |
336 KB |
Output is correct |
33 |
Correct |
36 ms |
24992 KB |
Output is correct |
34 |
Correct |
69 ms |
44848 KB |
Output is correct |
35 |
Correct |
51 ms |
44872 KB |
Output is correct |
36 |
Correct |
53 ms |
45032 KB |
Output is correct |
37 |
Correct |
42 ms |
45256 KB |
Output is correct |
38 |
Correct |
56 ms |
45680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
207 ms |
19784 KB |
Output is correct |
5 |
Correct |
672 ms |
44872 KB |
Output is correct |
6 |
Correct |
631 ms |
7080 KB |
Output is correct |
7 |
Correct |
646 ms |
44832 KB |
Output is correct |
8 |
Correct |
592 ms |
15048 KB |
Output is correct |
9 |
Correct |
930 ms |
44840 KB |
Output is correct |
10 |
Correct |
1274 ms |
44836 KB |
Output is correct |
11 |
Correct |
1142 ms |
44872 KB |
Output is correct |
12 |
Correct |
1214 ms |
44852 KB |
Output is correct |
13 |
Correct |
766 ms |
45000 KB |
Output is correct |
14 |
Correct |
1228 ms |
45244 KB |
Output is correct |
15 |
Correct |
966 ms |
45732 KB |
Output is correct |
16 |
Correct |
1096 ms |
45760 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
2 ms |
336 KB |
Output is correct |
20 |
Correct |
3 ms |
464 KB |
Output is correct |
21 |
Correct |
3 ms |
464 KB |
Output is correct |
22 |
Correct |
3 ms |
464 KB |
Output is correct |
23 |
Correct |
3 ms |
464 KB |
Output is correct |
24 |
Correct |
3 ms |
480 KB |
Output is correct |
25 |
Correct |
1 ms |
464 KB |
Output is correct |
26 |
Correct |
1 ms |
464 KB |
Output is correct |
27 |
Correct |
17 ms |
720 KB |
Output is correct |
28 |
Correct |
23 ms |
720 KB |
Output is correct |
29 |
Correct |
27 ms |
720 KB |
Output is correct |
30 |
Correct |
24 ms |
720 KB |
Output is correct |
31 |
Correct |
27 ms |
720 KB |
Output is correct |
32 |
Correct |
0 ms |
336 KB |
Output is correct |
33 |
Correct |
36 ms |
24992 KB |
Output is correct |
34 |
Correct |
69 ms |
44848 KB |
Output is correct |
35 |
Correct |
51 ms |
44872 KB |
Output is correct |
36 |
Correct |
53 ms |
45032 KB |
Output is correct |
37 |
Correct |
42 ms |
45256 KB |
Output is correct |
38 |
Correct |
56 ms |
45680 KB |
Output is correct |
39 |
Correct |
1 ms |
336 KB |
Output is correct |
40 |
Correct |
1 ms |
336 KB |
Output is correct |
41 |
Correct |
0 ms |
336 KB |
Output is correct |
42 |
Correct |
206 ms |
19924 KB |
Output is correct |
43 |
Correct |
863 ms |
44864 KB |
Output is correct |
44 |
Correct |
719 ms |
7120 KB |
Output is correct |
45 |
Correct |
1272 ms |
44872 KB |
Output is correct |
46 |
Correct |
673 ms |
15048 KB |
Output is correct |
47 |
Correct |
1102 ms |
44888 KB |
Output is correct |
48 |
Correct |
1164 ms |
44824 KB |
Output is correct |
49 |
Correct |
1217 ms |
44884 KB |
Output is correct |
50 |
Correct |
1419 ms |
44880 KB |
Output is correct |
51 |
Correct |
1113 ms |
44848 KB |
Output is correct |
52 |
Correct |
1238 ms |
45348 KB |
Output is correct |
53 |
Correct |
739 ms |
45728 KB |
Output is correct |
54 |
Correct |
756 ms |
45656 KB |
Output is correct |
55 |
Correct |
1 ms |
336 KB |
Output is correct |
56 |
Correct |
102 ms |
44852 KB |
Output is correct |
57 |
Correct |
946 ms |
44840 KB |
Output is correct |
58 |
Correct |
397 ms |
7504 KB |
Output is correct |
59 |
Correct |
857 ms |
44844 KB |
Output is correct |
60 |
Correct |
322 ms |
15560 KB |
Output is correct |
61 |
Correct |
830 ms |
44840 KB |
Output is correct |
62 |
Correct |
1364 ms |
44860 KB |
Output is correct |
63 |
Correct |
992 ms |
44868 KB |
Output is correct |
64 |
Correct |
1297 ms |
44872 KB |
Output is correct |
65 |
Correct |
1006 ms |
44956 KB |
Output is correct |
66 |
Correct |
1488 ms |
45256 KB |
Output is correct |
67 |
Correct |
1033 ms |
45692 KB |
Output is correct |
68 |
Correct |
913 ms |
45640 KB |
Output is correct |
69 |
Correct |
0 ms |
336 KB |
Output is correct |
70 |
Correct |
1 ms |
336 KB |
Output is correct |
71 |
Correct |
2 ms |
464 KB |
Output is correct |
72 |
Correct |
3 ms |
484 KB |
Output is correct |
73 |
Correct |
2 ms |
464 KB |
Output is correct |
74 |
Correct |
3 ms |
464 KB |
Output is correct |
75 |
Correct |
2 ms |
464 KB |
Output is correct |
76 |
Correct |
1 ms |
336 KB |
Output is correct |
77 |
Correct |
0 ms |
336 KB |
Output is correct |
78 |
Correct |
2 ms |
336 KB |
Output is correct |
79 |
Correct |
2 ms |
468 KB |
Output is correct |
80 |
Correct |
3 ms |
464 KB |
Output is correct |
81 |
Correct |
2 ms |
464 KB |
Output is correct |
82 |
Correct |
3 ms |
464 KB |
Output is correct |
83 |
Correct |
2 ms |
464 KB |
Output is correct |
84 |
Correct |
0 ms |
464 KB |
Output is correct |
85 |
Correct |
5 ms |
464 KB |
Output is correct |
86 |
Correct |
20 ms |
720 KB |
Output is correct |
87 |
Correct |
28 ms |
720 KB |
Output is correct |
88 |
Correct |
21 ms |
720 KB |
Output is correct |
89 |
Correct |
23 ms |
720 KB |
Output is correct |
90 |
Correct |
18 ms |
720 KB |
Output is correct |
91 |
Correct |
1 ms |
464 KB |
Output is correct |
92 |
Correct |
1 ms |
464 KB |
Output is correct |
93 |
Correct |
23 ms |
720 KB |
Output is correct |
94 |
Correct |
25 ms |
720 KB |
Output is correct |
95 |
Correct |
16 ms |
720 KB |
Output is correct |
96 |
Correct |
16 ms |
720 KB |
Output is correct |
97 |
Correct |
20 ms |
720 KB |
Output is correct |
98 |
Correct |
1 ms |
336 KB |
Output is correct |
99 |
Correct |
64 ms |
44844 KB |
Output is correct |
100 |
Correct |
54 ms |
44896 KB |
Output is correct |
101 |
Correct |
43 ms |
44856 KB |
Output is correct |
102 |
Correct |
62 ms |
44848 KB |
Output is correct |
103 |
Correct |
44 ms |
45348 KB |
Output is correct |
104 |
Correct |
44 ms |
45724 KB |
Output is correct |
105 |
Correct |
0 ms |
336 KB |
Output is correct |
106 |
Correct |
36 ms |
24948 KB |
Output is correct |
107 |
Correct |
48 ms |
44872 KB |
Output is correct |
108 |
Correct |
45 ms |
44852 KB |
Output is correct |
109 |
Correct |
51 ms |
44856 KB |
Output is correct |
110 |
Correct |
42 ms |
45256 KB |
Output is correct |
111 |
Correct |
46 ms |
45716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
178 ms |
36008 KB |
Output is correct |
4 |
Correct |
1341 ms |
44844 KB |
Output is correct |
5 |
Correct |
1068 ms |
21772 KB |
Output is correct |
6 |
Correct |
1318 ms |
44828 KB |
Output is correct |
7 |
Correct |
1096 ms |
30936 KB |
Output is correct |
8 |
Correct |
1407 ms |
44956 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
2 ms |
336 KB |
Output is correct |
14 |
Incorrect |
3 ms |
464 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |