#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> sp1[200200], sp2[200200], sp3[200200], sp4[200200], a;
int n, l[200200], r[200200];
int geth(int x){
if (x<0) return -1e9;
if (x>=n) return -1e9;
return a[x];
}
void init(int N, std::vector<int> H) {
n = N, a = H;
for (int i=0;i<n;i++){
sp1[i].push_back(H[i]);
sp2[i].push_back(H[i]);
}
for (int j=1;j<20;j++){
for (int i=0;i<n;i++){
if (i-(1<<j)+1<0) sp1[i].push_back(-1);
else sp1[i].push_back(max(sp1[i][j-1], sp1[i-(1<<(j-1))][j-1]));
if (i+(1<<j)-1>=n) sp2[i].push_back(-1);
else sp2[i].push_back(max(sp2[i][j-1], sp2[i+(1<<(j-1))][j-1]));
}
}
for (int i=0;i<n;i++){
int cur = i-1, cur2 = -1e9;
for (int j=19;j>=0;j--) if (cur!=-1 && sp1[cur][j]!=-1 && max(cur2, sp1[cur][j])<H[i]){
cur2 = max(cur2, sp1[cur][j]);
cur -= (1<<j);
}
l[i] = cur; cur = i+1, cur2 = -1e9;
for (int j=19;j>=0;j--) if (cur!=n && sp2[cur][j]!=-1 && sp2[cur][j]<H[i]){
cur2 = max(cur2, sp1[cur][j]);
cur += (1<<j);
}
r[i] = cur;
if (geth(l[i])>=geth(r[i])) sp3[i].push_back(l[i]);
else sp3[i].push_back(r[i]);
sp4[i].push_back(r[i]);
//printf("%d %d\n", l[i], r[i]);
}
for (int j=1;j<20;j++){
for (int i=0;i<n;i++){
if (sp3[i][j-1]==-1) sp3[i].push_back(-1);
else sp3[i].push_back(sp3[sp3[i][j-1]][j-1]);
if (sp4[i][j-1]==n) sp4[i].push_back(n);
else sp4[i].push_back(sp4[sp4[i][j-1]][j-1]);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int cur = A, ans = 0;
for (int j=19;j>=0;j--) if (sp3[cur][j]!=-1 && a[sp3[cur][j]]<a[C]) cur = sp3[cur][j], ans += (1<<j);
for (int j=19;j>=0;j--) if (sp4[cur][j]!=n && a[sp4[cur][j]]<=a[C]) cur = sp4[cur][j], ans += (1<<j);
if (cur!=C) return -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19016 KB |
Output is correct |
2 |
Correct |
11 ms |
19016 KB |
Output is correct |
3 |
Incorrect |
553 ms |
111892 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
19016 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
19016 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
19016 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19016 KB |
Output is correct |
2 |
Correct |
10 ms |
19016 KB |
Output is correct |
3 |
Correct |
11 ms |
19016 KB |
Output is correct |
4 |
Correct |
533 ms |
72468 KB |
Output is correct |
5 |
Correct |
1454 ms |
135748 KB |
Output is correct |
6 |
Correct |
888 ms |
38204 KB |
Output is correct |
7 |
Correct |
1580 ms |
135692 KB |
Output is correct |
8 |
Correct |
707 ms |
59328 KB |
Output is correct |
9 |
Correct |
1596 ms |
135660 KB |
Output is correct |
10 |
Correct |
1786 ms |
135856 KB |
Output is correct |
11 |
Correct |
1912 ms |
135660 KB |
Output is correct |
12 |
Correct |
1540 ms |
135744 KB |
Output is correct |
13 |
Correct |
1414 ms |
135796 KB |
Output is correct |
14 |
Correct |
1706 ms |
135700 KB |
Output is correct |
15 |
Correct |
1540 ms |
135616 KB |
Output is correct |
16 |
Correct |
1486 ms |
135640 KB |
Output is correct |
17 |
Correct |
11 ms |
19016 KB |
Output is correct |
18 |
Correct |
11 ms |
19016 KB |
Output is correct |
19 |
Correct |
12 ms |
19016 KB |
Output is correct |
20 |
Correct |
13 ms |
19272 KB |
Output is correct |
21 |
Correct |
13 ms |
19228 KB |
Output is correct |
22 |
Correct |
14 ms |
19272 KB |
Output is correct |
23 |
Correct |
13 ms |
19272 KB |
Output is correct |
24 |
Correct |
14 ms |
19272 KB |
Output is correct |
25 |
Correct |
11 ms |
19272 KB |
Output is correct |
26 |
Correct |
12 ms |
19528 KB |
Output is correct |
27 |
Correct |
38 ms |
20296 KB |
Output is correct |
28 |
Correct |
37 ms |
20296 KB |
Output is correct |
29 |
Correct |
39 ms |
20296 KB |
Output is correct |
30 |
Correct |
40 ms |
20296 KB |
Output is correct |
31 |
Correct |
24 ms |
20296 KB |
Output is correct |
32 |
Correct |
10 ms |
19040 KB |
Output is correct |
33 |
Correct |
306 ms |
86540 KB |
Output is correct |
34 |
Correct |
511 ms |
135728 KB |
Output is correct |
35 |
Correct |
538 ms |
135832 KB |
Output is correct |
36 |
Correct |
528 ms |
135688 KB |
Output is correct |
37 |
Correct |
595 ms |
135640 KB |
Output is correct |
38 |
Correct |
518 ms |
135616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19016 KB |
Output is correct |
2 |
Correct |
10 ms |
19016 KB |
Output is correct |
3 |
Correct |
11 ms |
19016 KB |
Output is correct |
4 |
Correct |
533 ms |
72468 KB |
Output is correct |
5 |
Correct |
1454 ms |
135748 KB |
Output is correct |
6 |
Correct |
888 ms |
38204 KB |
Output is correct |
7 |
Correct |
1580 ms |
135692 KB |
Output is correct |
8 |
Correct |
707 ms |
59328 KB |
Output is correct |
9 |
Correct |
1596 ms |
135660 KB |
Output is correct |
10 |
Correct |
1786 ms |
135856 KB |
Output is correct |
11 |
Correct |
1912 ms |
135660 KB |
Output is correct |
12 |
Correct |
1540 ms |
135744 KB |
Output is correct |
13 |
Correct |
1414 ms |
135796 KB |
Output is correct |
14 |
Correct |
1706 ms |
135700 KB |
Output is correct |
15 |
Correct |
1540 ms |
135616 KB |
Output is correct |
16 |
Correct |
1486 ms |
135640 KB |
Output is correct |
17 |
Correct |
11 ms |
19016 KB |
Output is correct |
18 |
Correct |
11 ms |
19016 KB |
Output is correct |
19 |
Correct |
12 ms |
19016 KB |
Output is correct |
20 |
Correct |
13 ms |
19272 KB |
Output is correct |
21 |
Correct |
13 ms |
19228 KB |
Output is correct |
22 |
Correct |
14 ms |
19272 KB |
Output is correct |
23 |
Correct |
13 ms |
19272 KB |
Output is correct |
24 |
Correct |
14 ms |
19272 KB |
Output is correct |
25 |
Correct |
11 ms |
19272 KB |
Output is correct |
26 |
Correct |
12 ms |
19528 KB |
Output is correct |
27 |
Correct |
38 ms |
20296 KB |
Output is correct |
28 |
Correct |
37 ms |
20296 KB |
Output is correct |
29 |
Correct |
39 ms |
20296 KB |
Output is correct |
30 |
Correct |
40 ms |
20296 KB |
Output is correct |
31 |
Correct |
24 ms |
20296 KB |
Output is correct |
32 |
Correct |
10 ms |
19040 KB |
Output is correct |
33 |
Correct |
306 ms |
86540 KB |
Output is correct |
34 |
Correct |
511 ms |
135728 KB |
Output is correct |
35 |
Correct |
538 ms |
135832 KB |
Output is correct |
36 |
Correct |
528 ms |
135688 KB |
Output is correct |
37 |
Correct |
595 ms |
135640 KB |
Output is correct |
38 |
Correct |
518 ms |
135616 KB |
Output is correct |
39 |
Correct |
11 ms |
19016 KB |
Output is correct |
40 |
Correct |
11 ms |
19052 KB |
Output is correct |
41 |
Correct |
11 ms |
19016 KB |
Output is correct |
42 |
Correct |
459 ms |
72364 KB |
Output is correct |
43 |
Correct |
1581 ms |
135720 KB |
Output is correct |
44 |
Correct |
918 ms |
38284 KB |
Output is correct |
45 |
Correct |
1625 ms |
135756 KB |
Output is correct |
46 |
Correct |
819 ms |
59236 KB |
Output is correct |
47 |
Correct |
1604 ms |
135640 KB |
Output is correct |
48 |
Correct |
1680 ms |
135772 KB |
Output is correct |
49 |
Correct |
1762 ms |
135712 KB |
Output is correct |
50 |
Correct |
1607 ms |
135672 KB |
Output is correct |
51 |
Correct |
1463 ms |
135720 KB |
Output is correct |
52 |
Correct |
1814 ms |
135636 KB |
Output is correct |
53 |
Correct |
1707 ms |
135692 KB |
Output is correct |
54 |
Correct |
1715 ms |
135804 KB |
Output is correct |
55 |
Correct |
13 ms |
19016 KB |
Output is correct |
56 |
Incorrect |
590 ms |
135376 KB |
Output isn't correct |
57 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19016 KB |
Output is correct |
2 |
Correct |
11 ms |
19016 KB |
Output is correct |
3 |
Incorrect |
553 ms |
111892 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |