#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
bool f = 1;
int n, s = 1;
vector<int> l, r, h;
vector<vector<int>> upmec, uppoqr;
vector<bool> used;
vector<pair<int, int>> seg;
void build(int l, int r, int u) {
if (l == r) {
if (l < n) seg[u] = { h[l], l };
else seg[u] = { 2e9, l };
return;
}
int m = (l + r) / 2;
build(l, m, 2 * u + 1), build(m + 1, r, 2 * u + 2);
seg[u] = min(seg[2 * u + 1], seg[2 * u + 2]);
}
pair<int, int> get(int l, int r, int lx, int rx, int u) {
if (lx >= l && rx <= r) return seg[u];
if (lx > r || rx < l) return { 2e9, -1 };
int m = (lx + rx) / 2;
return min(get(l, r, lx, m, 2 * u + 1), get(l, r, m + 1, rx, 2 * u + 2));
}
void calcDp(int u, vector<int> &dp, int c, int d){
if(dp[u] != -1) return;
if(u >= c && u <= d) {
dp[u] = 0;
return;
}
if(l[u] != -1 && r[u] != -1) {
calcDp(l[u], dp, c, d);
calcDp(r[u], dp, c, d);
dp[u] = min(dp[l[u]], dp[r[u]]) + 1;
}
else if(l[u] != -1) {
calcDp(l[u], dp, c, d);
dp[u] = dp[l[u]] + 1;
}
else if(r[u] != -1){
calcDp(r[u], dp, c, d);
dp[u] = dp[r[u]] + 1;
}
else dp[u] = 1e9;
}
void calcUp(int u){
if(used[u]) return;
used[u] = 1;
if(r[u] != -1 && l[u] != -1){
if(h[r[u]] > h[l[u]]){
calcUp(r[u]), calcUp(l[u]);
upmec[u][0] = r[u];
uppoqr[u][0] = l[u];
for(int i = 1; i < 20; i++){
if(upmec[u][i - 1] == -1) upmec[u][i] = -1;
else upmec[u][i] = upmec[upmec[u][i - 1]][i - 1];
if(uppoqr[u][i - 1] == -1) uppoqr[u][i] = -1;
else uppoqr[u][i] = uppoqr[uppoqr[u][i - 1]][i - 1];
}
}
else{
calcUp(r[u]), calcUp(l[u]);
upmec[u][0] = l[u];
uppoqr[u][0] = r[u];
for(int i = 1; i < 20; i++){
if(upmec[u][i - 1] == -1) upmec[u][i] = -1;
else upmec[u][i] = upmec[upmec[u][i - 1]][i - 1];
if(uppoqr[u][i - 1] == -1) uppoqr[u][i] = -1;
else uppoqr[u][i] = uppoqr[uppoqr[u][i - 1]][i - 1];
}
}
}
else if(r[u] != -1){
calcUp(r[u]);
upmec[u][0] = uppoqr[u][0] = r[u];
for(int i = 1; i < 20; i++){
if(upmec[u][i - 1] == -1) upmec[u][i] = uppoqr[u][i] = -1;
else upmec[u][i] = uppoqr[u][i] = upmec[upmec[u][i - 1]][i - 1];
}
}
else if(l[u] != -1){
calcUp(l[u]);
upmec[u][0] = uppoqr[u][0] = l[u];
for(int i = 1; i < 20; i++){
if(upmec[u][i - 1] == -1) upmec[u][i] = uppoqr[u][i] = -1;
else upmec[u][i] = uppoqr[u][i] = upmec[upmec[u][i - 1]][i - 1];
}
}
else {
for(int i = 0; i < 20; i++) uppoqr[u][i] = upmec[u][i] = -1;
}
}
void init(int N, vector<int> H) {
n = N, h = H;
l = r = vector<int> (n, -1);
while(s < n) s <<= 1;
seg.resize(2 * s);
build(0, s - 1, 0);
upmec = uppoqr = vector<vector<int>> (n, vector<int> (20));
used = vector<bool> (n);
for(int i = 0; i < n; i++) if(h[i] != i + 1) f = 0;
if(f) return;
stack<pair<int, int>> st;
st.push({1e9, -1});
for(int i = n - 1; i >= 0; i--){
while(st.top().first < h[i]){
st.pop();
}
r[i] = st.top().second;
st.push({h[i], i});
}
while(st.size())st.pop();
st.push({1e9, -1});
for(int i = 0; i < n; i++){
while(st.top().first < h[i]){
st.pop();
}
l[i] = st.top().second;
st.push({h[i], i});
}
for(int i = 0; i < n; i++) {
if(!used[i]) calcUp(i);
}
// up[i][j]
}
int minimum_jumps(int A, int B, int C, int D) {
if(f) return C - B;
int ans = 0;
if(C == D){
pair<int, int> pp = get(A, B, 0, s - 1, 0);
int node = pp.second;
for(int i = 19; i >= 0; i--){
if(upmec[node][i] == -1) continue;
if(h[upmec[node][i]] <= h[C]){
ans += (1 << i);
node = upmec[node][i];
}
}
for(int i = 19; i >= 0; i--){
if(uppoqr[node][i] == -1) continue;
if(h[uppoqr[node][i]] <= h[C]){
ans += (1 << i);
node = uppoqr[node][i];
}
}
if(node == C) return ans;
else return -1;
}
vector<int> dp(n, -1);
for(int i = A; i <= B; i++) calcDp(i, dp, C, D);
ans = 2e9;
for(int i = A; i <= B; i++){
ans = min(ans, dp[i]);
}
if (ans >= 1e9) return -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
115 ms |
44828 KB |
Output is correct |
4 |
Correct |
839 ms |
55192 KB |
Output is correct |
5 |
Correct |
829 ms |
27892 KB |
Output is correct |
6 |
Correct |
840 ms |
55240 KB |
Output is correct |
7 |
Correct |
614 ms |
39192 KB |
Output is correct |
8 |
Correct |
893 ms |
55196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Incorrect |
2 ms |
208 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Incorrect |
2 ms |
208 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
66 ms |
45360 KB |
Output is correct |
6 |
Correct |
98 ms |
55344 KB |
Output is correct |
7 |
Correct |
41 ms |
28348 KB |
Output is correct |
8 |
Correct |
84 ms |
55212 KB |
Output is correct |
9 |
Correct |
13 ms |
8528 KB |
Output is correct |
10 |
Correct |
83 ms |
55428 KB |
Output is correct |
11 |
Correct |
55 ms |
55196 KB |
Output is correct |
12 |
Correct |
91 ms |
60304 KB |
Output is correct |
13 |
Correct |
87 ms |
60808 KB |
Output is correct |
14 |
Correct |
82 ms |
55308 KB |
Output is correct |
15 |
Correct |
167 ms |
58444 KB |
Output is correct |
16 |
Correct |
104 ms |
58056 KB |
Output is correct |
17 |
Correct |
109 ms |
58076 KB |
Output is correct |
18 |
Correct |
0 ms |
208 KB |
Output is correct |
19 |
Correct |
0 ms |
336 KB |
Output is correct |
20 |
Correct |
0 ms |
336 KB |
Output is correct |
21 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
280 ms |
25632 KB |
Output is correct |
5 |
Correct |
957 ms |
55312 KB |
Output is correct |
6 |
Correct |
650 ms |
9704 KB |
Output is correct |
7 |
Correct |
718 ms |
55240 KB |
Output is correct |
8 |
Correct |
581 ms |
19868 KB |
Output is correct |
9 |
Correct |
1004 ms |
55240 KB |
Output is correct |
10 |
Correct |
881 ms |
55240 KB |
Output is correct |
11 |
Correct |
1020 ms |
61648 KB |
Output is correct |
12 |
Correct |
1117 ms |
62128 KB |
Output is correct |
13 |
Correct |
906 ms |
55308 KB |
Output is correct |
14 |
Correct |
961 ms |
56092 KB |
Output is correct |
15 |
Correct |
901 ms |
56968 KB |
Output is correct |
16 |
Correct |
651 ms |
56904 KB |
Output is correct |
17 |
Correct |
0 ms |
208 KB |
Output is correct |
18 |
Correct |
0 ms |
208 KB |
Output is correct |
19 |
Correct |
2 ms |
208 KB |
Output is correct |
20 |
Correct |
2 ms |
336 KB |
Output is correct |
21 |
Correct |
2 ms |
336 KB |
Output is correct |
22 |
Correct |
1 ms |
336 KB |
Output is correct |
23 |
Correct |
3 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
0 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
464 KB |
Output is correct |
27 |
Correct |
21 ms |
720 KB |
Output is correct |
28 |
Correct |
22 ms |
848 KB |
Output is correct |
29 |
Correct |
21 ms |
720 KB |
Output is correct |
30 |
Correct |
22 ms |
720 KB |
Output is correct |
31 |
Correct |
19 ms |
720 KB |
Output is correct |
32 |
Correct |
0 ms |
208 KB |
Output is correct |
33 |
Correct |
50 ms |
31704 KB |
Output is correct |
34 |
Correct |
82 ms |
55332 KB |
Output is correct |
35 |
Correct |
86 ms |
61980 KB |
Output is correct |
36 |
Correct |
79 ms |
55216 KB |
Output is correct |
37 |
Correct |
160 ms |
56040 KB |
Output is correct |
38 |
Correct |
103 ms |
56992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
280 ms |
25632 KB |
Output is correct |
5 |
Correct |
957 ms |
55312 KB |
Output is correct |
6 |
Correct |
650 ms |
9704 KB |
Output is correct |
7 |
Correct |
718 ms |
55240 KB |
Output is correct |
8 |
Correct |
581 ms |
19868 KB |
Output is correct |
9 |
Correct |
1004 ms |
55240 KB |
Output is correct |
10 |
Correct |
881 ms |
55240 KB |
Output is correct |
11 |
Correct |
1020 ms |
61648 KB |
Output is correct |
12 |
Correct |
1117 ms |
62128 KB |
Output is correct |
13 |
Correct |
906 ms |
55308 KB |
Output is correct |
14 |
Correct |
961 ms |
56092 KB |
Output is correct |
15 |
Correct |
901 ms |
56968 KB |
Output is correct |
16 |
Correct |
651 ms |
56904 KB |
Output is correct |
17 |
Correct |
0 ms |
208 KB |
Output is correct |
18 |
Correct |
0 ms |
208 KB |
Output is correct |
19 |
Correct |
2 ms |
208 KB |
Output is correct |
20 |
Correct |
2 ms |
336 KB |
Output is correct |
21 |
Correct |
2 ms |
336 KB |
Output is correct |
22 |
Correct |
1 ms |
336 KB |
Output is correct |
23 |
Correct |
3 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
0 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
464 KB |
Output is correct |
27 |
Correct |
21 ms |
720 KB |
Output is correct |
28 |
Correct |
22 ms |
848 KB |
Output is correct |
29 |
Correct |
21 ms |
720 KB |
Output is correct |
30 |
Correct |
22 ms |
720 KB |
Output is correct |
31 |
Correct |
19 ms |
720 KB |
Output is correct |
32 |
Correct |
0 ms |
208 KB |
Output is correct |
33 |
Correct |
50 ms |
31704 KB |
Output is correct |
34 |
Correct |
82 ms |
55332 KB |
Output is correct |
35 |
Correct |
86 ms |
61980 KB |
Output is correct |
36 |
Correct |
79 ms |
55216 KB |
Output is correct |
37 |
Correct |
160 ms |
56040 KB |
Output is correct |
38 |
Correct |
103 ms |
56992 KB |
Output is correct |
39 |
Correct |
0 ms |
208 KB |
Output is correct |
40 |
Correct |
0 ms |
208 KB |
Output is correct |
41 |
Correct |
0 ms |
208 KB |
Output is correct |
42 |
Correct |
264 ms |
25624 KB |
Output is correct |
43 |
Correct |
1002 ms |
55308 KB |
Output is correct |
44 |
Correct |
597 ms |
9680 KB |
Output is correct |
45 |
Correct |
859 ms |
55316 KB |
Output is correct |
46 |
Correct |
622 ms |
19772 KB |
Output is correct |
47 |
Correct |
787 ms |
55312 KB |
Output is correct |
48 |
Correct |
780 ms |
55240 KB |
Output is correct |
49 |
Correct |
1046 ms |
61684 KB |
Output is correct |
50 |
Correct |
1071 ms |
62108 KB |
Output is correct |
51 |
Correct |
971 ms |
55368 KB |
Output is correct |
52 |
Correct |
1139 ms |
56048 KB |
Output is correct |
53 |
Correct |
1065 ms |
56904 KB |
Output is correct |
54 |
Correct |
1094 ms |
56904 KB |
Output is correct |
55 |
Correct |
0 ms |
208 KB |
Output is correct |
56 |
Incorrect |
120 ms |
55116 KB |
Output isn't correct |
57 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
115 ms |
44828 KB |
Output is correct |
4 |
Correct |
839 ms |
55192 KB |
Output is correct |
5 |
Correct |
829 ms |
27892 KB |
Output is correct |
6 |
Correct |
840 ms |
55240 KB |
Output is correct |
7 |
Correct |
614 ms |
39192 KB |
Output is correct |
8 |
Correct |
893 ms |
55196 KB |
Output is correct |
9 |
Correct |
0 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
11 |
Correct |
0 ms |
208 KB |
Output is correct |
12 |
Correct |
0 ms |
208 KB |
Output is correct |
13 |
Incorrect |
2 ms |
208 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |