#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 200000;
const int Log = 18;
int N;
int low[MaxN][Log], high[MaxN][Log];
int lf[MaxN][Log], rg[MaxN][Log];
int rmq[MaxN][Log];
vector<int> H;
void init(int _N, vector<int> _H) {
N = _N, H = _H;
stack<int> st;
for (int i = 0; i < N; i++){
while (!st.empty() && H[st.top()] < H[i]) st.pop();
lf[i][0] = (st.empty() ? -1 : st.top());
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = N - 1; i >= 0; i--){
while (!st.empty() && H[st.top()] < H[i]) st.pop();
rg[i][0] = (st.empty() ? -1 : st.top());
st.push(i);
}
memset(low, -1, sizeof(low));
memset(high, -1, sizeof(high));
for (int i = 0; i < N; i++){
int l = lf[i][0], r = rg[i][0];
if (l == -1 && r == -1) continue;
if (l != -1 && r != -1){
low[i][0] = (H[l] < H[r] ? l : r);
high[i][0] = (H[l] > H[r] ? l : r);
} else {
low[i][0] = high[i][0] = (l != -1 ? l : r);
}
}
for (int j = 1; j < Log; j++){
for (int i = 0; i < N; i++){
if (low[i][j - 1] != -1){
low[i][j] = low[low[i][j - 1]][j - 1];
}
if (high[i][j - 1] != -1){
high[i][j] = high[high[i][j - 1]][j - 1];
}
if (lf[i][j - 1] != -1){
lf[i][j] = lf[lf[i][j - 1]][j - 1];
} else {
lf[i][j] = -1;
}
if (rg[i][j - 1] != -1){
rg[i][j] = rg[rg[i][j - 1]][j - 1];
} else {
rg[i][j] = -1;
}
}
}
for (int i = 0; i < N; i++) rmq[i][0] = H[i];
for (int j = 1; j < Log; j++){
for (int i = 0; i + (1 << j) - 1 < N; i++){
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int z = 31 - __builtin_clz(D - C + 1);
int mx = max(rmq[C][z], rmq[D - (1 << z) + 1][z]);
int ans = 0;
int v = B;
for (int i = Log - 1; i >= 0; i--){
int u = lf[v][i];
if (u != -1 && u >= A && H[u] <= mx) v = u;
}
for (int i = Log - 1; i >= 0; i--){
int u = high[v][i];
if (u != -1 && u < C && H[u] <= mx){
ans += 1 << i;
v = u;
}
}
for (int i = Log - 1; i >= 0; i--){
int u = rg[v][i];
if (u != -1 && u < C){
ans += 1 << i;
v = u;
}
}
if (v < C){
v = rg[v][0];
ans++;
}
return (C <= v && v <= D ? ans : -1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
28496 KB |
Output is correct |
2 |
Correct |
10 ms |
28476 KB |
Output is correct |
3 |
Correct |
170 ms |
64592 KB |
Output is correct |
4 |
Correct |
961 ms |
73916 KB |
Output is correct |
5 |
Correct |
833 ms |
51344 KB |
Output is correct |
6 |
Correct |
745 ms |
73912 KB |
Output is correct |
7 |
Correct |
656 ms |
59516 KB |
Output is correct |
8 |
Correct |
966 ms |
73916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
28496 KB |
Output is correct |
2 |
Correct |
12 ms |
28424 KB |
Output is correct |
3 |
Correct |
10 ms |
28496 KB |
Output is correct |
4 |
Correct |
10 ms |
28428 KB |
Output is correct |
5 |
Correct |
12 ms |
28492 KB |
Output is correct |
6 |
Incorrect |
12 ms |
28496 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
28496 KB |
Output is correct |
2 |
Correct |
12 ms |
28424 KB |
Output is correct |
3 |
Correct |
10 ms |
28496 KB |
Output is correct |
4 |
Correct |
10 ms |
28428 KB |
Output is correct |
5 |
Correct |
12 ms |
28492 KB |
Output is correct |
6 |
Incorrect |
12 ms |
28496 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
28496 KB |
Output is correct |
2 |
Correct |
9 ms |
28496 KB |
Output is correct |
3 |
Correct |
10 ms |
28496 KB |
Output is correct |
4 |
Correct |
10 ms |
28420 KB |
Output is correct |
5 |
Correct |
91 ms |
64292 KB |
Output is correct |
6 |
Correct |
112 ms |
73020 KB |
Output is correct |
7 |
Correct |
64 ms |
51284 KB |
Output is correct |
8 |
Correct |
112 ms |
73092 KB |
Output is correct |
9 |
Correct |
20 ms |
35188 KB |
Output is correct |
10 |
Correct |
103 ms |
73092 KB |
Output is correct |
11 |
Correct |
105 ms |
73900 KB |
Output is correct |
12 |
Correct |
99 ms |
73636 KB |
Output is correct |
13 |
Correct |
97 ms |
73680 KB |
Output is correct |
14 |
Correct |
104 ms |
72996 KB |
Output is correct |
15 |
Incorrect |
125 ms |
73364 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
28496 KB |
Output is correct |
2 |
Correct |
11 ms |
28496 KB |
Output is correct |
3 |
Correct |
11 ms |
28496 KB |
Output is correct |
4 |
Correct |
220 ms |
48852 KB |
Output is correct |
5 |
Correct |
877 ms |
73092 KB |
Output is correct |
6 |
Correct |
625 ms |
35912 KB |
Output is correct |
7 |
Correct |
900 ms |
73020 KB |
Output is correct |
8 |
Correct |
500 ms |
43756 KB |
Output is correct |
9 |
Correct |
912 ms |
73028 KB |
Output is correct |
10 |
Correct |
991 ms |
73800 KB |
Output is correct |
11 |
Correct |
903 ms |
73800 KB |
Output is correct |
12 |
Correct |
848 ms |
73804 KB |
Output is correct |
13 |
Correct |
697 ms |
73016 KB |
Output is correct |
14 |
Correct |
840 ms |
73464 KB |
Output is correct |
15 |
Correct |
948 ms |
73904 KB |
Output is correct |
16 |
Correct |
571 ms |
73912 KB |
Output is correct |
17 |
Correct |
12 ms |
28444 KB |
Output is correct |
18 |
Correct |
10 ms |
28488 KB |
Output is correct |
19 |
Correct |
11 ms |
28480 KB |
Output is correct |
20 |
Correct |
12 ms |
28496 KB |
Output is correct |
21 |
Correct |
14 ms |
28532 KB |
Output is correct |
22 |
Correct |
11 ms |
28480 KB |
Output is correct |
23 |
Correct |
12 ms |
28496 KB |
Output is correct |
24 |
Correct |
12 ms |
28496 KB |
Output is correct |
25 |
Correct |
12 ms |
28496 KB |
Output is correct |
26 |
Correct |
11 ms |
28624 KB |
Output is correct |
27 |
Correct |
32 ms |
28880 KB |
Output is correct |
28 |
Correct |
28 ms |
28880 KB |
Output is correct |
29 |
Correct |
21 ms |
28832 KB |
Output is correct |
30 |
Correct |
20 ms |
28880 KB |
Output is correct |
31 |
Correct |
27 ms |
28924 KB |
Output is correct |
32 |
Correct |
10 ms |
28496 KB |
Output is correct |
33 |
Correct |
59 ms |
54320 KB |
Output is correct |
34 |
Correct |
101 ms |
73148 KB |
Output is correct |
35 |
Correct |
102 ms |
73760 KB |
Output is correct |
36 |
Correct |
97 ms |
73008 KB |
Output is correct |
37 |
Correct |
126 ms |
73360 KB |
Output is correct |
38 |
Correct |
109 ms |
73916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
28496 KB |
Output is correct |
2 |
Correct |
11 ms |
28496 KB |
Output is correct |
3 |
Correct |
11 ms |
28496 KB |
Output is correct |
4 |
Correct |
220 ms |
48852 KB |
Output is correct |
5 |
Correct |
877 ms |
73092 KB |
Output is correct |
6 |
Correct |
625 ms |
35912 KB |
Output is correct |
7 |
Correct |
900 ms |
73020 KB |
Output is correct |
8 |
Correct |
500 ms |
43756 KB |
Output is correct |
9 |
Correct |
912 ms |
73028 KB |
Output is correct |
10 |
Correct |
991 ms |
73800 KB |
Output is correct |
11 |
Correct |
903 ms |
73800 KB |
Output is correct |
12 |
Correct |
848 ms |
73804 KB |
Output is correct |
13 |
Correct |
697 ms |
73016 KB |
Output is correct |
14 |
Correct |
840 ms |
73464 KB |
Output is correct |
15 |
Correct |
948 ms |
73904 KB |
Output is correct |
16 |
Correct |
571 ms |
73912 KB |
Output is correct |
17 |
Correct |
12 ms |
28444 KB |
Output is correct |
18 |
Correct |
10 ms |
28488 KB |
Output is correct |
19 |
Correct |
11 ms |
28480 KB |
Output is correct |
20 |
Correct |
12 ms |
28496 KB |
Output is correct |
21 |
Correct |
14 ms |
28532 KB |
Output is correct |
22 |
Correct |
11 ms |
28480 KB |
Output is correct |
23 |
Correct |
12 ms |
28496 KB |
Output is correct |
24 |
Correct |
12 ms |
28496 KB |
Output is correct |
25 |
Correct |
12 ms |
28496 KB |
Output is correct |
26 |
Correct |
11 ms |
28624 KB |
Output is correct |
27 |
Correct |
32 ms |
28880 KB |
Output is correct |
28 |
Correct |
28 ms |
28880 KB |
Output is correct |
29 |
Correct |
21 ms |
28832 KB |
Output is correct |
30 |
Correct |
20 ms |
28880 KB |
Output is correct |
31 |
Correct |
27 ms |
28924 KB |
Output is correct |
32 |
Correct |
10 ms |
28496 KB |
Output is correct |
33 |
Correct |
59 ms |
54320 KB |
Output is correct |
34 |
Correct |
101 ms |
73148 KB |
Output is correct |
35 |
Correct |
102 ms |
73760 KB |
Output is correct |
36 |
Correct |
97 ms |
73008 KB |
Output is correct |
37 |
Correct |
126 ms |
73360 KB |
Output is correct |
38 |
Correct |
109 ms |
73916 KB |
Output is correct |
39 |
Correct |
11 ms |
28464 KB |
Output is correct |
40 |
Correct |
11 ms |
28496 KB |
Output is correct |
41 |
Correct |
10 ms |
28496 KB |
Output is correct |
42 |
Correct |
234 ms |
48848 KB |
Output is correct |
43 |
Correct |
904 ms |
73124 KB |
Output is correct |
44 |
Correct |
581 ms |
35824 KB |
Output is correct |
45 |
Correct |
953 ms |
73032 KB |
Output is correct |
46 |
Correct |
480 ms |
43804 KB |
Output is correct |
47 |
Correct |
851 ms |
72964 KB |
Output is correct |
48 |
Correct |
885 ms |
73928 KB |
Output is correct |
49 |
Correct |
951 ms |
73764 KB |
Output is correct |
50 |
Correct |
1029 ms |
73760 KB |
Output is correct |
51 |
Correct |
909 ms |
73132 KB |
Output is correct |
52 |
Correct |
818 ms |
73456 KB |
Output is correct |
53 |
Correct |
819 ms |
73936 KB |
Output is correct |
54 |
Correct |
880 ms |
73800 KB |
Output is correct |
55 |
Correct |
11 ms |
28496 KB |
Output is correct |
56 |
Correct |
139 ms |
72920 KB |
Output is correct |
57 |
Correct |
697 ms |
73016 KB |
Output is correct |
58 |
Correct |
411 ms |
36304 KB |
Output is correct |
59 |
Correct |
867 ms |
73000 KB |
Output is correct |
60 |
Correct |
326 ms |
44348 KB |
Output is correct |
61 |
Correct |
868 ms |
73096 KB |
Output is correct |
62 |
Correct |
917 ms |
73920 KB |
Output is correct |
63 |
Correct |
926 ms |
73704 KB |
Output is correct |
64 |
Correct |
995 ms |
73504 KB |
Output is correct |
65 |
Correct |
679 ms |
73000 KB |
Output is correct |
66 |
Correct |
1037 ms |
73444 KB |
Output is correct |
67 |
Correct |
907 ms |
73912 KB |
Output is correct |
68 |
Correct |
970 ms |
73796 KB |
Output is correct |
69 |
Correct |
10 ms |
28496 KB |
Output is correct |
70 |
Correct |
10 ms |
28496 KB |
Output is correct |
71 |
Correct |
13 ms |
28512 KB |
Output is correct |
72 |
Correct |
12 ms |
28496 KB |
Output is correct |
73 |
Correct |
11 ms |
28496 KB |
Output is correct |
74 |
Correct |
12 ms |
28496 KB |
Output is correct |
75 |
Correct |
11 ms |
28428 KB |
Output is correct |
76 |
Correct |
11 ms |
28452 KB |
Output is correct |
77 |
Correct |
11 ms |
28496 KB |
Output is correct |
78 |
Correct |
11 ms |
28496 KB |
Output is correct |
79 |
Correct |
13 ms |
28496 KB |
Output is correct |
80 |
Correct |
12 ms |
28476 KB |
Output is correct |
81 |
Correct |
12 ms |
28496 KB |
Output is correct |
82 |
Correct |
11 ms |
28496 KB |
Output is correct |
83 |
Correct |
12 ms |
28496 KB |
Output is correct |
84 |
Correct |
11 ms |
28496 KB |
Output is correct |
85 |
Correct |
13 ms |
28464 KB |
Output is correct |
86 |
Correct |
27 ms |
28860 KB |
Output is correct |
87 |
Correct |
29 ms |
28880 KB |
Output is correct |
88 |
Correct |
29 ms |
28908 KB |
Output is correct |
89 |
Correct |
28 ms |
28880 KB |
Output is correct |
90 |
Correct |
26 ms |
28880 KB |
Output is correct |
91 |
Correct |
10 ms |
28524 KB |
Output is correct |
92 |
Correct |
11 ms |
28624 KB |
Output is correct |
93 |
Correct |
28 ms |
28856 KB |
Output is correct |
94 |
Correct |
27 ms |
28880 KB |
Output is correct |
95 |
Correct |
23 ms |
28904 KB |
Output is correct |
96 |
Correct |
22 ms |
28880 KB |
Output is correct |
97 |
Correct |
28 ms |
28880 KB |
Output is correct |
98 |
Correct |
10 ms |
28496 KB |
Output is correct |
99 |
Correct |
105 ms |
72992 KB |
Output is correct |
100 |
Correct |
101 ms |
73048 KB |
Output is correct |
101 |
Correct |
97 ms |
73664 KB |
Output is correct |
102 |
Correct |
99 ms |
73072 KB |
Output is correct |
103 |
Correct |
122 ms |
73348 KB |
Output is correct |
104 |
Correct |
99 ms |
73888 KB |
Output is correct |
105 |
Correct |
10 ms |
28408 KB |
Output is correct |
106 |
Correct |
60 ms |
54220 KB |
Output is correct |
107 |
Correct |
109 ms |
73164 KB |
Output is correct |
108 |
Correct |
98 ms |
73672 KB |
Output is correct |
109 |
Correct |
99 ms |
72980 KB |
Output is correct |
110 |
Correct |
123 ms |
73344 KB |
Output is correct |
111 |
Correct |
101 ms |
73920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
28496 KB |
Output is correct |
2 |
Correct |
10 ms |
28476 KB |
Output is correct |
3 |
Correct |
170 ms |
64592 KB |
Output is correct |
4 |
Correct |
961 ms |
73916 KB |
Output is correct |
5 |
Correct |
833 ms |
51344 KB |
Output is correct |
6 |
Correct |
745 ms |
73912 KB |
Output is correct |
7 |
Correct |
656 ms |
59516 KB |
Output is correct |
8 |
Correct |
966 ms |
73916 KB |
Output is correct |
9 |
Correct |
10 ms |
28496 KB |
Output is correct |
10 |
Correct |
12 ms |
28424 KB |
Output is correct |
11 |
Correct |
10 ms |
28496 KB |
Output is correct |
12 |
Correct |
10 ms |
28428 KB |
Output is correct |
13 |
Correct |
12 ms |
28492 KB |
Output is correct |
14 |
Incorrect |
12 ms |
28496 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |