#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int LOG = 21;
vector<int>T, H;
int n, m;
int sp[N][LOG];
void build_sparse()
{
for (int i = 0; i < m; i++)
sp[i][0] = H[i];
for (int j = 1; j < LOG; j++)
{
for (int i = 0; i < m; i++)
{
if (i + (1 << j) - 1 >= m)continue;
sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r)
{
int lg = log2(r - l + 1);
return max(sp[l][lg], sp[r - (1 << lg) + 1][lg]);
}
bool is_free(int i, int j)
{
return T[i] > H[j];
}
void initialize(std::vector<int> T, std::vector<int> H) {
n = T.size();
m = H.size();
(::T).resize(n);
(::H).resize(m);
for (int i = 0; i < n; i++)(::T)[i] = T[i];
for (int i = 0; i < m; i++)(::H)[i] = H[i];
build_sparse();
}
bool can_reach(int L, int R, int S, int D)
{
assert(n == 1);
if (S > D)
swap(S, D);
if (T[0] > query(S, D))
return true;
else return false;
}
