#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define print(a) for(auto x : a) cout << x << ' '; cout << endl;
vector<int> mq, a;
vector<vector<int>> rm;
vector<int> lt, rt;
int n;
bool sub1 = 1;
void build(){
rm.resize(mq[n] + 1);
rm[0] = a;
for (int q = 1; (1 << q) <= n; q++){
rm[q].resize(n - (1 << q) + 1);
for (int i = 0; i < n - (1 << q) + 1; i++)
rm[q][i] = max(rm[q - 1][i], rm[q - 1][i + (1 << (q - 1))]);
}
}
void init(int N, vector<int> h) {
for(int i = 0; i < n; i ++)
if(h[i] != i + 1)
sub1 = 0;
a = h;
n = N;
mq.resize(n + 2);
for(int i = 2; i < n + 2; i ++)
mq[i] = mq[i / 2] + 1;
build();
lt.resize(n);
rt.resize(n);
for(int i = 0; i < n; i ++){
int l = -1, r = i - 1;
while(l < r){
int mid = (l + r + 1) >> 1;
if(max(rm[mq[i - mid]][mid], rm[mq[i - mid]][i - (1 << mq[i - mid])]) > a[i])
l = mid;
else
r = mid - 1;
}
lt[i] = l;
l = i + 1, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(max(rm[mq[mid - i]][i], rm[mq[mid - i]][mid + 1 - (1 << mq[mid - i])]) > a[i])
r = mid;
else
l = mid + 1;
}
rt[i] = r;
}
}
int minimum_jumps(int A, int B, int C, int D){
if(sub1)
return C - B;
int ans = 1e9, cnt = 0;
int index = A;
while(rt[index] <= B)
index = rt[index];
while(index < C){
if(rt[index] == n or rt[index] > D)
break;
if(C <= rt[index] and rt[index] <= D){
ans = min(ans, cnt + 1);
break;
}
if(lt[index] != -1 and rt[lt[index]] != n and rt[rt[index]] < rt[lt[index]] and rt[lt[index]] <= D)
cnt ++, index = lt[index];
else{
cnt ++;
index = rt[index];
}
}
index = B;
while(A <= lt[index] and rt[lt[index]] <= D)
index = lt[index];
cnt = 0;
while(index < C){
if (rt[index] == n or rt[index] > D)
break;
if (C <= rt[index] and rt[index] <= D){
ans = min(ans, cnt + 1);
break;
}
if (lt[index] != -1 and rt[lt[index]] != n and rt[rt[index]] < rt[lt[index]] and rt[lt[index]] <= D)
cnt++, index = lt[index];
else
{
cnt++;
index = rt[index];
}
}
if(ans == 1e9)
return -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
113 ms |
14396 KB |
Output is correct |
4 |
Correct |
649 ms |
18244 KB |
Output is correct |
5 |
Correct |
539 ms |
9048 KB |
Output is correct |
6 |
Correct |
649 ms |
18244 KB |
Output is correct |
7 |
Correct |
495 ms |
12236 KB |
Output is correct |
8 |
Correct |
612 ms |
18112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
113 ms |
14396 KB |
Output is correct |
4 |
Correct |
649 ms |
18244 KB |
Output is correct |
5 |
Correct |
539 ms |
9048 KB |
Output is correct |
6 |
Correct |
649 ms |
18244 KB |
Output is correct |
7 |
Correct |
495 ms |
12236 KB |
Output is correct |
8 |
Correct |
612 ms |
18112 KB |
Output is correct |
9 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |