#include "jumps.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 200007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int a[M], l[M][20], r[M][20], hi[M][20];
void init(int n, int H[])
{
for(int i = 1; i <= n; ++i) a[i] = H[i - 1];
vector <int> v;
for(int i = 1; i <= n; ++i){
while(v.size() && a[v.back()] <= a[i]) v.pop_back();
if(v.size()) l[i][0] = v.back();
else l[i][0] = i;
v.pb(i);
}
v.clear();
for(int i = n; i; --i){
while(v.size() && a[v.back()] < a[i]) v.pop_back();
if(v.size()) r[i][0] = v.back();
else r[i][0] = i;
v.pb(i);
}
for(int i = 1; i <= n; ++i) hi[i][0] = (a[r[i][0]] > a[l[i][0]] ? r[i][0] : l[i][0]);
for(int j = 1; j < 20; ++j){
for(int i = 1; i <= n; ++i){
l[i][j] = l[l[i][j - 1]][j - 1];
r[i][j] = r[r[i][j - 1]][j - 1];
hi[i][j] = hi[hi[i][j - 1]][j - 1];
}
}
return;
}
int get(int A, int B)
{
for(int i = 19; i >= 0; --i)
if(r[A][i] <= B)
A = r[A][i];
return A;
}
int minimum_jumps(int A, int B, int C, int D)
{
++A; ++B; ++C; ++D;
if(B + 1 == C) return (r[B][0] <= D ? 1 : -1);
int mid = get(B + 1, C - 1);
if(a[B] > a[mid]) return (r[B][0] <= D ? 1 : -1);
int p = B;
for(int i = 19; i >= 0; --i)
if(l[p][i] >= A && a[l[p][i]] < a[mid])
p = l[p][i];
if(l[p][0] >= A && r[l[p][0]][0] <= D) return 1;
int ret = 0;
for(int i = 19; i >= 0; --i){
if(hi[p][i] <= a[mid]){
ret += (1 << i);
p = hi[p][i];
}
}
if(p == mid) return (r[p][0] <= D ? ret + 1 : -1);
if(a[l[p][0]] > a[mid] && r[l[p][0]][0] <= D) return ret + 2;
for(int i = 19; i >= 0; --i){
if(r[p][i] < C){
ret += (1 << i);
p = r[p][i];
}
}
return (r[p][0] >= C && r[p][0] <= D ? ret + 1 : -1);
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)
Compilation message
/usr/bin/ld: /tmp/ccaaSPun.o: in function `main':
stub.cpp:(.text.startup+0x177): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
