#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#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;
if (H[v] > mx) return -1;
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 |
11 ms |
28496 KB |
Output is correct |
3 |
Correct |
173 ms |
64668 KB |
Output is correct |
4 |
Correct |
891 ms |
73920 KB |
Output is correct |
5 |
Correct |
516 ms |
51332 KB |
Output is correct |
6 |
Correct |
1036 ms |
73876 KB |
Output is correct |
7 |
Correct |
668 ms |
59464 KB |
Output is correct |
8 |
Correct |
823 ms |
73876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
28508 KB |
Output is correct |
2 |
Correct |
11 ms |
28492 KB |
Output is correct |
3 |
Correct |
11 ms |
28500 KB |
Output is correct |
4 |
Correct |
11 ms |
28460 KB |
Output is correct |
5 |
Correct |
12 ms |
28504 KB |
Output is correct |
6 |
Incorrect |
13 ms |
28496 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
28508 KB |
Output is correct |
2 |
Correct |
11 ms |
28492 KB |
Output is correct |
3 |
Correct |
11 ms |
28500 KB |
Output is correct |
4 |
Correct |
11 ms |
28460 KB |
Output is correct |
5 |
Correct |
12 ms |
28504 KB |
Output is correct |
6 |
Incorrect |
13 ms |
28496 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
28496 KB |
Output is correct |
2 |
Correct |
10 ms |
28496 KB |
Output is correct |
3 |
Correct |
11 ms |
28496 KB |
Output is correct |
4 |
Correct |
11 ms |
28496 KB |
Output is correct |
5 |
Correct |
81 ms |
64284 KB |
Output is correct |
6 |
Correct |
106 ms |
73020 KB |
Output is correct |
7 |
Correct |
54 ms |
51296 KB |
Output is correct |
8 |
Correct |
100 ms |
73032 KB |
Output is correct |
9 |
Correct |
20 ms |
35140 KB |
Output is correct |
10 |
Correct |
119 ms |
73012 KB |
Output is correct |
11 |
Correct |
105 ms |
74312 KB |
Output is correct |
12 |
Correct |
102 ms |
73648 KB |
Output is correct |
13 |
Correct |
100 ms |
73600 KB |
Output is correct |
14 |
Correct |
114 ms |
72992 KB |
Output is correct |
15 |
Incorrect |
130 ms |
73332 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 |
13 ms |
28496 KB |
Output is correct |
3 |
Correct |
11 ms |
28496 KB |
Output is correct |
4 |
Correct |
235 ms |
48864 KB |
Output is correct |
5 |
Correct |
778 ms |
73212 KB |
Output is correct |
6 |
Correct |
583 ms |
35836 KB |
Output is correct |
7 |
Correct |
859 ms |
73104 KB |
Output is correct |
8 |
Correct |
430 ms |
43776 KB |
Output is correct |
9 |
Correct |
821 ms |
73012 KB |
Output is correct |
10 |
Correct |
885 ms |
73920 KB |
Output is correct |
11 |
Correct |
979 ms |
73836 KB |
Output is correct |
12 |
Correct |
762 ms |
73804 KB |
Output is correct |
13 |
Correct |
731 ms |
73096 KB |
Output is correct |
14 |
Correct |
839 ms |
73456 KB |
Output is correct |
15 |
Correct |
810 ms |
73916 KB |
Output is correct |
16 |
Correct |
755 ms |
73800 KB |
Output is correct |
17 |
Correct |
11 ms |
28496 KB |
Output is correct |
18 |
Correct |
12 ms |
28492 KB |
Output is correct |
19 |
Correct |
12 ms |
28496 KB |
Output is correct |
20 |
Correct |
13 ms |
28496 KB |
Output is correct |
21 |
Correct |
13 ms |
28496 KB |
Output is correct |
22 |
Correct |
13 ms |
28624 KB |
Output is correct |
23 |
Correct |
13 ms |
28496 KB |
Output is correct |
24 |
Correct |
13 ms |
28496 KB |
Output is correct |
25 |
Correct |
11 ms |
28496 KB |
Output is correct |
26 |
Correct |
11 ms |
28624 KB |
Output is correct |
27 |
Correct |
29 ms |
28880 KB |
Output is correct |
28 |
Correct |
23 ms |
28924 KB |
Output is correct |
29 |
Correct |
28 ms |
28880 KB |
Output is correct |
30 |
Correct |
20 ms |
28872 KB |
Output is correct |
31 |
Correct |
28 ms |
28880 KB |
Output is correct |
32 |
Correct |
11 ms |
28496 KB |
Output is correct |
33 |
Correct |
66 ms |
54320 KB |
Output is correct |
34 |
Correct |
101 ms |
72996 KB |
Output is correct |
35 |
Correct |
103 ms |
73768 KB |
Output is correct |
36 |
Correct |
127 ms |
73092 KB |
Output is correct |
37 |
Correct |
140 ms |
73360 KB |
Output is correct |
38 |
Correct |
101 ms |
73788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
28496 KB |
Output is correct |
2 |
Correct |
13 ms |
28496 KB |
Output is correct |
3 |
Correct |
11 ms |
28496 KB |
Output is correct |
4 |
Correct |
235 ms |
48864 KB |
Output is correct |
5 |
Correct |
778 ms |
73212 KB |
Output is correct |
6 |
Correct |
583 ms |
35836 KB |
Output is correct |
7 |
Correct |
859 ms |
73104 KB |
Output is correct |
8 |
Correct |
430 ms |
43776 KB |
Output is correct |
9 |
Correct |
821 ms |
73012 KB |
Output is correct |
10 |
Correct |
885 ms |
73920 KB |
Output is correct |
11 |
Correct |
979 ms |
73836 KB |
Output is correct |
12 |
Correct |
762 ms |
73804 KB |
Output is correct |
13 |
Correct |
731 ms |
73096 KB |
Output is correct |
14 |
Correct |
839 ms |
73456 KB |
Output is correct |
15 |
Correct |
810 ms |
73916 KB |
Output is correct |
16 |
Correct |
755 ms |
73800 KB |
Output is correct |
17 |
Correct |
11 ms |
28496 KB |
Output is correct |
18 |
Correct |
12 ms |
28492 KB |
Output is correct |
19 |
Correct |
12 ms |
28496 KB |
Output is correct |
20 |
Correct |
13 ms |
28496 KB |
Output is correct |
21 |
Correct |
13 ms |
28496 KB |
Output is correct |
22 |
Correct |
13 ms |
28624 KB |
Output is correct |
23 |
Correct |
13 ms |
28496 KB |
Output is correct |
24 |
Correct |
13 ms |
28496 KB |
Output is correct |
25 |
Correct |
11 ms |
28496 KB |
Output is correct |
26 |
Correct |
11 ms |
28624 KB |
Output is correct |
27 |
Correct |
29 ms |
28880 KB |
Output is correct |
28 |
Correct |
23 ms |
28924 KB |
Output is correct |
29 |
Correct |
28 ms |
28880 KB |
Output is correct |
30 |
Correct |
20 ms |
28872 KB |
Output is correct |
31 |
Correct |
28 ms |
28880 KB |
Output is correct |
32 |
Correct |
11 ms |
28496 KB |
Output is correct |
33 |
Correct |
66 ms |
54320 KB |
Output is correct |
34 |
Correct |
101 ms |
72996 KB |
Output is correct |
35 |
Correct |
103 ms |
73768 KB |
Output is correct |
36 |
Correct |
127 ms |
73092 KB |
Output is correct |
37 |
Correct |
140 ms |
73360 KB |
Output is correct |
38 |
Correct |
101 ms |
73788 KB |
Output is correct |
39 |
Correct |
11 ms |
28496 KB |
Output is correct |
40 |
Correct |
11 ms |
28388 KB |
Output is correct |
41 |
Correct |
12 ms |
28488 KB |
Output is correct |
42 |
Correct |
257 ms |
48848 KB |
Output is correct |
43 |
Correct |
623 ms |
72992 KB |
Output is correct |
44 |
Correct |
394 ms |
35840 KB |
Output is correct |
45 |
Correct |
797 ms |
73092 KB |
Output is correct |
46 |
Correct |
277 ms |
43752 KB |
Output is correct |
47 |
Correct |
570 ms |
73056 KB |
Output is correct |
48 |
Correct |
1004 ms |
73920 KB |
Output is correct |
49 |
Correct |
923 ms |
73800 KB |
Output is correct |
50 |
Correct |
827 ms |
73804 KB |
Output is correct |
51 |
Correct |
820 ms |
73088 KB |
Output is correct |
52 |
Correct |
988 ms |
73456 KB |
Output is correct |
53 |
Correct |
779 ms |
73792 KB |
Output is correct |
54 |
Correct |
684 ms |
73920 KB |
Output is correct |
55 |
Correct |
11 ms |
28464 KB |
Output is correct |
56 |
Correct |
142 ms |
72852 KB |
Output is correct |
57 |
Correct |
818 ms |
72992 KB |
Output is correct |
58 |
Correct |
378 ms |
36304 KB |
Output is correct |
59 |
Correct |
811 ms |
73032 KB |
Output is correct |
60 |
Correct |
373 ms |
44348 KB |
Output is correct |
61 |
Correct |
824 ms |
73096 KB |
Output is correct |
62 |
Correct |
891 ms |
73912 KB |
Output is correct |
63 |
Correct |
903 ms |
73584 KB |
Output is correct |
64 |
Correct |
915 ms |
73620 KB |
Output is correct |
65 |
Correct |
824 ms |
73100 KB |
Output is correct |
66 |
Correct |
937 ms |
73452 KB |
Output is correct |
67 |
Correct |
830 ms |
73916 KB |
Output is correct |
68 |
Correct |
833 ms |
73800 KB |
Output is correct |
69 |
Correct |
11 ms |
28496 KB |
Output is correct |
70 |
Correct |
11 ms |
28496 KB |
Output is correct |
71 |
Correct |
13 ms |
28472 KB |
Output is correct |
72 |
Correct |
13 ms |
28492 KB |
Output is correct |
73 |
Correct |
12 ms |
28496 KB |
Output is correct |
74 |
Correct |
13 ms |
28520 KB |
Output is correct |
75 |
Correct |
12 ms |
28496 KB |
Output is correct |
76 |
Correct |
11 ms |
28496 KB |
Output is correct |
77 |
Correct |
11 ms |
28496 KB |
Output is correct |
78 |
Correct |
14 ms |
28496 KB |
Output is correct |
79 |
Correct |
11 ms |
28496 KB |
Output is correct |
80 |
Correct |
12 ms |
28496 KB |
Output is correct |
81 |
Correct |
13 ms |
28496 KB |
Output is correct |
82 |
Correct |
12 ms |
28496 KB |
Output is correct |
83 |
Correct |
13 ms |
28516 KB |
Output is correct |
84 |
Correct |
11 ms |
28472 KB |
Output is correct |
85 |
Correct |
14 ms |
28464 KB |
Output is correct |
86 |
Correct |
26 ms |
28880 KB |
Output is correct |
87 |
Correct |
19 ms |
28876 KB |
Output is correct |
88 |
Correct |
28 ms |
28880 KB |
Output is correct |
89 |
Correct |
28 ms |
28944 KB |
Output is correct |
90 |
Correct |
21 ms |
28864 KB |
Output is correct |
91 |
Correct |
11 ms |
28496 KB |
Output is correct |
92 |
Correct |
11 ms |
28748 KB |
Output is correct |
93 |
Correct |
29 ms |
28880 KB |
Output is correct |
94 |
Correct |
30 ms |
28880 KB |
Output is correct |
95 |
Correct |
20 ms |
28880 KB |
Output is correct |
96 |
Correct |
31 ms |
28844 KB |
Output is correct |
97 |
Correct |
18 ms |
28896 KB |
Output is correct |
98 |
Correct |
10 ms |
28504 KB |
Output is correct |
99 |
Correct |
98 ms |
72912 KB |
Output is correct |
100 |
Correct |
109 ms |
73092 KB |
Output is correct |
101 |
Correct |
113 ms |
73624 KB |
Output is correct |
102 |
Correct |
102 ms |
73100 KB |
Output is correct |
103 |
Correct |
142 ms |
73452 KB |
Output is correct |
104 |
Correct |
113 ms |
73908 KB |
Output is correct |
105 |
Correct |
11 ms |
28428 KB |
Output is correct |
106 |
Correct |
61 ms |
54264 KB |
Output is correct |
107 |
Correct |
101 ms |
73096 KB |
Output is correct |
108 |
Correct |
102 ms |
73768 KB |
Output is correct |
109 |
Correct |
101 ms |
73112 KB |
Output is correct |
110 |
Correct |
126 ms |
73360 KB |
Output is correct |
111 |
Correct |
104 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 |
173 ms |
64668 KB |
Output is correct |
4 |
Correct |
891 ms |
73920 KB |
Output is correct |
5 |
Correct |
516 ms |
51332 KB |
Output is correct |
6 |
Correct |
1036 ms |
73876 KB |
Output is correct |
7 |
Correct |
668 ms |
59464 KB |
Output is correct |
8 |
Correct |
823 ms |
73876 KB |
Output is correct |
9 |
Correct |
13 ms |
28508 KB |
Output is correct |
10 |
Correct |
11 ms |
28492 KB |
Output is correct |
11 |
Correct |
11 ms |
28500 KB |
Output is correct |
12 |
Correct |
11 ms |
28460 KB |
Output is correct |
13 |
Correct |
12 ms |
28504 KB |
Output is correct |
14 |
Incorrect |
13 ms |
28496 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |