#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
const int LG = 18;
int n, l[N], r[N], toL[N][LG], toR[N][LG], maxH[N][LG];
vector<int> h;
void initEdges()
{
vector<pair<int, int>> sortedH;
for (int i = 0; i < n; i++)
sortedH.push_back({h[i], i});
sort(sortedH.begin(), sortedH.end(), greater<pair<int, int>>());
set<int> s;
s.insert(-1);
s.insert(n);
for (auto [_, i] : sortedH)
{
auto it = s.lower_bound(i);
r[i] = *it;
l[i] = *(--it);
s.insert(i);
}
}
void constructTable()
{
memset(toL, -1, sizeof toL);
memset(toR, -1, sizeof toR);
for (int i = 0; i < n; i++)
{
toL[i][0] = l[i];
toR[i][0] = r[i];
maxH[i][0] = h[i];
}
for (int j = 0; j + 1 < LG; j++)
for (int i = 0; i < n; i++)
{
if (toL[i][j] >= 0)
toL[i][j + 1] = toL[toL[i][j]][j];
if (toR[i][j] >= 0)
toR[i][j + 1] = toR[toR[i][j]][j];
if (i + (1 << j) < n)
maxH[i][j + 1] = max(maxH[i][j], maxH[i + (1 << j)][j]);
}
}
void init(int N, vector<int> H) {
n = N;
h = H;
h[n] = 0;
initEdges();
constructTable();
}
int getMaxH(int l, int r)
{
int bit = 31 - __builtin_clz(r - l + 1);
return max(maxH[l][bit], maxH[r - (1 << bit) + 1][bit]);
}
int between(int x, int y, int z)
{
return y <= x && x <= z;
}
int calcDist(int s, int from, int to, int maxDestH)
{
int dist = 0;
for (int i = LG - 1; i >= 0; i--)
{
int x = toR[s][i];
if (x >= 0 && x < from && h[x] < maxDestH)
{
dist |= 1 << i;
s = x;
}
}
s = toR[s][0];
return between(s, from, to) ? dist + 1 : n;
}
int minimum_jumps(int A, int B, int C, int D) {
int s = B, maxDestH = getMaxH(C, D);
for (int i = LG - 1; i >= 0; i--)
{
int x = toL[s][i];
if (x >= A && x < n && h[x] < maxDestH)
s = x;
}
if (h[s] > maxDestH)
return -1;
if (between(l[s], C, D) || between(r[s], C, D))
return 1;
int ans = calcDist(s, C, D, maxDestH);
if (l[s] >= 0 && l[s] < n)
ans = min(ans, calcDist(l[s], C, D, maxDestH) + 1);
return ans < n ? ans : -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
28488 KB |
Output is correct |
2 |
Correct |
12 ms |
28480 KB |
Output is correct |
3 |
Correct |
302 ms |
50224 KB |
Output is correct |
4 |
Correct |
970 ms |
56052 KB |
Output is correct |
5 |
Correct |
1161 ms |
42272 KB |
Output is correct |
6 |
Correct |
1392 ms |
55792 KB |
Output is correct |
7 |
Correct |
1060 ms |
47200 KB |
Output is correct |
8 |
Correct |
1299 ms |
55812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
28492 KB |
Output is correct |
2 |
Correct |
14 ms |
28488 KB |
Output is correct |
3 |
Correct |
13 ms |
28488 KB |
Output is correct |
4 |
Correct |
13 ms |
28488 KB |
Output is correct |
5 |
Correct |
18 ms |
28488 KB |
Output is correct |
6 |
Correct |
15 ms |
28488 KB |
Output is correct |
7 |
Correct |
17 ms |
28512 KB |
Output is correct |
8 |
Incorrect |
16 ms |
28432 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
28492 KB |
Output is correct |
2 |
Correct |
14 ms |
28488 KB |
Output is correct |
3 |
Correct |
13 ms |
28488 KB |
Output is correct |
4 |
Correct |
13 ms |
28488 KB |
Output is correct |
5 |
Correct |
18 ms |
28488 KB |
Output is correct |
6 |
Correct |
15 ms |
28488 KB |
Output is correct |
7 |
Correct |
17 ms |
28512 KB |
Output is correct |
8 |
Incorrect |
16 ms |
28432 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
28444 KB |
Output is correct |
2 |
Correct |
15 ms |
28488 KB |
Output is correct |
3 |
Correct |
14 ms |
28488 KB |
Output is correct |
4 |
Correct |
16 ms |
28488 KB |
Output is correct |
5 |
Correct |
186 ms |
50580 KB |
Output is correct |
6 |
Correct |
302 ms |
55896 KB |
Output is correct |
7 |
Correct |
114 ms |
42508 KB |
Output is correct |
8 |
Correct |
262 ms |
55976 KB |
Output is correct |
9 |
Runtime error |
9 ms |
1096 KB |
Execution killed with signal 6 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
28616 KB |
Output is correct |
2 |
Correct |
13 ms |
28472 KB |
Output is correct |
3 |
Correct |
13 ms |
28488 KB |
Output is correct |
4 |
Incorrect |
409 ms |
40936 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
28616 KB |
Output is correct |
2 |
Correct |
13 ms |
28472 KB |
Output is correct |
3 |
Correct |
13 ms |
28488 KB |
Output is correct |
4 |
Incorrect |
409 ms |
40936 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
28488 KB |
Output is correct |
2 |
Correct |
12 ms |
28480 KB |
Output is correct |
3 |
Correct |
302 ms |
50224 KB |
Output is correct |
4 |
Correct |
970 ms |
56052 KB |
Output is correct |
5 |
Correct |
1161 ms |
42272 KB |
Output is correct |
6 |
Correct |
1392 ms |
55792 KB |
Output is correct |
7 |
Correct |
1060 ms |
47200 KB |
Output is correct |
8 |
Correct |
1299 ms |
55812 KB |
Output is correct |
9 |
Correct |
16 ms |
28492 KB |
Output is correct |
10 |
Correct |
14 ms |
28488 KB |
Output is correct |
11 |
Correct |
13 ms |
28488 KB |
Output is correct |
12 |
Correct |
13 ms |
28488 KB |
Output is correct |
13 |
Correct |
18 ms |
28488 KB |
Output is correct |
14 |
Correct |
15 ms |
28488 KB |
Output is correct |
15 |
Correct |
17 ms |
28512 KB |
Output is correct |
16 |
Incorrect |
16 ms |
28432 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |