#include <bits/stdc++.h>
using namespace std;
#define int long long
int L[200002][18];
int arr[200001];
int rarr[200001];
int R[200002][18];
int n;
void init(int32_t N, vector<int32_t> H) {
n=N;
for(int i=0;i<N;i++)arr[i]=H[i];
for(int i=0;i<N;i++)rarr[arr[i]]=i;
stack<int> q;
for(int i=0;i<N;i++){
while(!q.empty() and q.top()<arr[i])q.pop();
if(!q.empty())L[arr[i]][0]=q.top();
else L[arr[i]][0]=n+1;
q.emplace(arr[i]);
}
while(!q.empty())q.pop();
for(int i=N-1;i>=0;i--){
while(!q.empty() and q.top()<arr[i])q.pop();
if(!q.empty())R[arr[i]][0]=q.top();
else R[arr[i]][0]=n+1;
q.emplace(arr[i]);
}
for(int bit=0;bit<=17;bit++)L[n+1][bit]=R[n+1][bit]=n+1;
for(int i=1;i<=N;i++)if(L[i][0] > R[i][0])swap(L[i][0], R[i][0]);
for(int bit=1;bit<=17;bit++){
for(int i=1;i<=N;i++){
R[i][bit] = R[R[i][bit - 1]][bit - 1];
}
}
for(int bit=1;bit<=17;bit++){
for(int i=1;i<=N;i++){
L[i][bit] = L[L[i][bit - 1]][bit - 1];
}
}
}
int32_t minimum_jumps(int32_t A, int32_t B, int32_t C, int32_t D) {
int base = arr[A];
int tar = arr[C];
int ans = 0;
for(int jump=17;jump>=0;jump--){
if(R[base][jump] <= tar) { base = R[base][jump]; ans+=(1 << jump);}
}
for(int jump=17;jump>=0;jump--){
if(L[base][jump] <= tar) { base = L[base][jump]; ans+=(1 << jump);}
}
return base==tar ? ans : -1;
}
//int32_t main() {
// int32_t N, Q;
// assert(2 == scanf("%d %d", &N, &Q));
// std::vector<int32_t> H(N);
// for (int32_t i = 0; i < N; ++i) {
// assert(1 == scanf("%d", &H[i]));
// }
// init(N, H);
//
// for (int32_t i = 0; i < Q; ++i) {
// int32_t A, B, C, D;
// assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
// printf("%d\n", minimum_jumps(A, B, C, D));
// }
// return 0;
//}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6484 KB |
Output is correct |
2 |
Correct |
1 ms |
6488 KB |
Output is correct |
3 |
Incorrect |
138 ms |
54316 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6488 KB |
Output is correct |
3 |
Correct |
2 ms |
6484 KB |
Output is correct |
4 |
Correct |
166 ms |
34136 KB |
Output is correct |
5 |
Correct |
675 ms |
61260 KB |
Output is correct |
6 |
Correct |
420 ms |
17240 KB |
Output is correct |
7 |
Correct |
699 ms |
61560 KB |
Output is correct |
8 |
Correct |
368 ms |
25552 KB |
Output is correct |
9 |
Correct |
681 ms |
61452 KB |
Output is correct |
10 |
Correct |
767 ms |
63016 KB |
Output is correct |
11 |
Correct |
760 ms |
62912 KB |
Output is correct |
12 |
Correct |
800 ms |
62780 KB |
Output is correct |
13 |
Correct |
668 ms |
61484 KB |
Output is correct |
14 |
Correct |
776 ms |
62152 KB |
Output is correct |
15 |
Correct |
678 ms |
62920 KB |
Output is correct |
16 |
Correct |
674 ms |
63124 KB |
Output is correct |
17 |
Correct |
1 ms |
6488 KB |
Output is correct |
18 |
Correct |
1 ms |
6488 KB |
Output is correct |
19 |
Correct |
2 ms |
6740 KB |
Output is correct |
20 |
Correct |
2 ms |
6488 KB |
Output is correct |
21 |
Correct |
2 ms |
6488 KB |
Output is correct |
22 |
Correct |
2 ms |
6488 KB |
Output is correct |
23 |
Correct |
2 ms |
6488 KB |
Output is correct |
24 |
Correct |
2 ms |
6488 KB |
Output is correct |
25 |
Correct |
1 ms |
6488 KB |
Output is correct |
26 |
Correct |
1 ms |
6488 KB |
Output is correct |
27 |
Correct |
12 ms |
8792 KB |
Output is correct |
28 |
Correct |
14 ms |
8792 KB |
Output is correct |
29 |
Correct |
11 ms |
8792 KB |
Output is correct |
30 |
Correct |
12 ms |
8792 KB |
Output is correct |
31 |
Correct |
16 ms |
9044 KB |
Output is correct |
32 |
Correct |
1 ms |
6740 KB |
Output is correct |
33 |
Correct |
36 ms |
40484 KB |
Output is correct |
34 |
Correct |
81 ms |
61480 KB |
Output is correct |
35 |
Correct |
77 ms |
62836 KB |
Output is correct |
36 |
Correct |
79 ms |
61260 KB |
Output is correct |
37 |
Correct |
80 ms |
62172 KB |
Output is correct |
38 |
Correct |
75 ms |
62932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6488 KB |
Output is correct |
3 |
Correct |
2 ms |
6484 KB |
Output is correct |
4 |
Correct |
166 ms |
34136 KB |
Output is correct |
5 |
Correct |
675 ms |
61260 KB |
Output is correct |
6 |
Correct |
420 ms |
17240 KB |
Output is correct |
7 |
Correct |
699 ms |
61560 KB |
Output is correct |
8 |
Correct |
368 ms |
25552 KB |
Output is correct |
9 |
Correct |
681 ms |
61452 KB |
Output is correct |
10 |
Correct |
767 ms |
63016 KB |
Output is correct |
11 |
Correct |
760 ms |
62912 KB |
Output is correct |
12 |
Correct |
800 ms |
62780 KB |
Output is correct |
13 |
Correct |
668 ms |
61484 KB |
Output is correct |
14 |
Correct |
776 ms |
62152 KB |
Output is correct |
15 |
Correct |
678 ms |
62920 KB |
Output is correct |
16 |
Correct |
674 ms |
63124 KB |
Output is correct |
17 |
Correct |
1 ms |
6488 KB |
Output is correct |
18 |
Correct |
1 ms |
6488 KB |
Output is correct |
19 |
Correct |
2 ms |
6740 KB |
Output is correct |
20 |
Correct |
2 ms |
6488 KB |
Output is correct |
21 |
Correct |
2 ms |
6488 KB |
Output is correct |
22 |
Correct |
2 ms |
6488 KB |
Output is correct |
23 |
Correct |
2 ms |
6488 KB |
Output is correct |
24 |
Correct |
2 ms |
6488 KB |
Output is correct |
25 |
Correct |
1 ms |
6488 KB |
Output is correct |
26 |
Correct |
1 ms |
6488 KB |
Output is correct |
27 |
Correct |
12 ms |
8792 KB |
Output is correct |
28 |
Correct |
14 ms |
8792 KB |
Output is correct |
29 |
Correct |
11 ms |
8792 KB |
Output is correct |
30 |
Correct |
12 ms |
8792 KB |
Output is correct |
31 |
Correct |
16 ms |
9044 KB |
Output is correct |
32 |
Correct |
1 ms |
6740 KB |
Output is correct |
33 |
Correct |
36 ms |
40484 KB |
Output is correct |
34 |
Correct |
81 ms |
61480 KB |
Output is correct |
35 |
Correct |
77 ms |
62836 KB |
Output is correct |
36 |
Correct |
79 ms |
61260 KB |
Output is correct |
37 |
Correct |
80 ms |
62172 KB |
Output is correct |
38 |
Correct |
75 ms |
62932 KB |
Output is correct |
39 |
Correct |
1 ms |
6488 KB |
Output is correct |
40 |
Correct |
1 ms |
6488 KB |
Output is correct |
41 |
Correct |
1 ms |
6488 KB |
Output is correct |
42 |
Correct |
153 ms |
34064 KB |
Output is correct |
43 |
Correct |
693 ms |
61392 KB |
Output is correct |
44 |
Correct |
410 ms |
17240 KB |
Output is correct |
45 |
Correct |
687 ms |
61380 KB |
Output is correct |
46 |
Correct |
374 ms |
25688 KB |
Output is correct |
47 |
Correct |
689 ms |
61392 KB |
Output is correct |
48 |
Correct |
727 ms |
62928 KB |
Output is correct |
49 |
Correct |
684 ms |
63000 KB |
Output is correct |
50 |
Correct |
822 ms |
62836 KB |
Output is correct |
51 |
Correct |
677 ms |
61492 KB |
Output is correct |
52 |
Correct |
745 ms |
62120 KB |
Output is correct |
53 |
Correct |
674 ms |
62920 KB |
Output is correct |
54 |
Correct |
689 ms |
62892 KB |
Output is correct |
55 |
Correct |
1 ms |
6488 KB |
Output is correct |
56 |
Incorrect |
109 ms |
61296 KB |
Output isn't correct |
57 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6484 KB |
Output is correct |
2 |
Correct |
1 ms |
6488 KB |
Output is correct |
3 |
Incorrect |
138 ms |
54316 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |