#include "obstacles.h"
#include <algorithm>
class SegmentTree
{
int n;
std::vector<int> t;
public:
SegmentTree()
{
}
SegmentTree(const std::vector<int> &a)
{
n = a.size();
t = std::vector<int>(2 * n);
for (int i = 0; i < n; i++)
t[i + n] = a[i];
Build();
}
void Build()
{
for (int i = n - 1; i > 0; --i)
t[i] = std::max(t[i << 1], t[i << 1 | 1]);
}
void Modify(int p, int value)
{
for (t[p += n] = value; p > 1; p >>= 1)
t[p >> 1] = std::max(t[p], t[p ^ 1]);
}
int Query(int l, int r)
{
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1)
{
if ((l & 1) == 1)
res = std::max(res, t[l++]);
if ((r & 1) == 1)
res = std::max(res, t[--r]);
}
return res;
}
};
std::vector<int> TT;
std::vector<int> HH;
SegmentTree tr;
void initialize(std::vector<int> T, std::vector<int> H)
{
TT = T;
HH = H;
tr = SegmentTree(H);
}
bool can_reach(int L, int R, int S, int D)
{
if (S > D)
std::swap(S, D);
return TT[0] > tr.Query(S, D + 1);
}
