#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int subtask = 1;
int n;
vector<int> nums, l, r;
vector<vector<int>> liftBig, liftRight;
bool invalid(int k) {
if(k == -1 || k == n) return true;
return false;
}
int bigger(int a, int b) {
if(invalid(a) && invalid(b)) return -1;
if(invalid(a)) return b;
if(invalid(b)) return a;
if(nums[a] > nums[b]) return a;
return b;
}
void init(int N, std::vector<int> H) {
bool subtask1 = true;
for(int i = 0; i < N; i++) {
if(H[i] != i+1) subtask1 = false;
H[i]--;
}
if(subtask1) subtask = 1;
else subtask = 2;
n = N;
nums = H;
l.resize(n, -1);
r.resize(n, n);
liftBig.resize(n, vector<int>(20));
liftRight.resize(n, vector<int>(20));
vector<int> v;
v.push_back(0);
for(int i = 1; i < n; i++) {
while(v.size()) {
if(nums[v.back()] < nums[i]) {
r[v.back()] = i;
v.pop_back();
}
else break;
}
v.push_back(i);
}
v.clear();
v.push_back(n-1);
for(int i = n-2; i >= 0; i--) {
while(v.size()) {
if(nums[v.back()] < nums[i]) {
l[v.back()] = i;
v.pop_back();
}
else break;
}
v.push_back(i);
}
for(int j = 0; j < N; j++) {
liftBig[j][0] = bigger(l[j], r[j]);
if(r[j] == n) liftRight[j][0] = -1;
else liftRight[j][0] = r[j];
}
for(int i = 1; i < 20; i++) {
for(int j = 0; j < N; j++) {
if(liftBig[j][i-1] == -1) liftBig[j][i] = -1;
else liftBig[j][i] = liftBig[liftBig[j][i-1]][i-1];
if(liftRight[j][i-1] == -1) liftRight[j][i] = -1;
else liftRight[j][i] = liftRight[liftRight[j][i-1]][i-1];
}
}
}
int reachable(int x, int C, int D) {
if(C <= x && x <= D) return 0;
if(x > D) return -1;
int ans2 = BIG, tot = 0;
for(int i = 19; i >= 0; i--) {
if(liftRight[x][i] == -1) continue;
if(liftRight[x][i] > D) continue;
if(liftRight[x][i] >= C) ans2 = min(ans2, tot + (1 << i));
else {
x = liftRight[x][i];
tot += (1 << i);
}
}
return -1;
}
int BIG = 1e9 + 7;
int single_min_jumps(int x, int C, int D) {
int ans = BIG;
int tot = 0;
for(int i = 19; i >= 0; i--) {
if(liftBig[x][i] == -1) continue;
int r = reachable(liftBig[x][i], C, D);
if(r == -1) continue;
ans = min(ans, tot + (1 << i) + r);
if(r != 0) {
x = liftBig[x][i];
tot += (1 << i);
}
}
return ans;
}
int minimum_jumps(int A, int B, int C, int D) {
if(subtask == 1) {
return C - B;
}
int ans = BIG;
for(int i = A; i <= B; i++) {
ans = min(ans, single_min_jumps(i, C, D));
}
if(ans == BIG) return -1;
return ans;
}
Compilation message
jumps.cpp: In function 'int reachable(int, int, int)':
jumps.cpp:81:16: error: 'BIG' was not declared in this scope; did you mean 'EFBIG'?
81 | int ans2 = BIG, tot = 0;
| ^~~
| EFBIG
jumps.cpp:85:51: error: 'tot' was not declared in this scope
85 | if(liftRight[x][i] >= C) ans2 = min(ans2, tot + (1 << i));
| ^~~
jumps.cpp:88:13: error: 'tot' was not declared in this scope
88 | tot += (1 << i);
| ^~~
