#include "obstacles.h"
#include <algorithm>
#include <climits>
class SegmentTreeMax
{
int n;
std::vector<int> t;
public:
SegmentTreeMax()
{
}
SegmentTreeMax(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 = -1;
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;
}
};
class SegmentTreeMin
{
int n;
std::vector<int> t;
public:
SegmentTreeMin()
{
}
SegmentTreeMin(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::min(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::min(t[p], t[p ^ 1]);
}
int Query(int l, int r)
{
int res = INT_MAX;
for (l += n, r += n; l < r; l >>= 1, r >>= 1)
{
if ((l & 1) == 1)
res = std::min(res, t[l++]);
if ((r & 1) == 1)
res = std::min(res, t[--r]);
}
return res;
}
};
std::vector<int> TT;
std::vector<int> HH;
SegmentTreeMax tt_max;
SegmentTreeMin tt_min;
SegmentTreeMax hh_max;
SegmentTreeMin hh_min;
int N;
int M;
void initialize(std::vector<int> T, std::vector<int> H)
{
N = T.size();
M = H.size();
TT = T;
HH = H;
hh_max = SegmentTreeMax(H);
hh_min = SegmentTreeMin(H);
tt_max = SegmentTreeMax(T);
tt_min = SegmentTreeMin(T);
}
int BigLeft(SegmentTreeMax &tr, int i, int value)
{
int l = -1, r = i + 1;
while (l + 1 < r)
{
int m = (l + r) >> 1;
if (tr.Query(m, i + 1) > value)
l = m;
else
r = m;
}
return l;
}
int BigRight(SegmentTreeMax &tr, int i, int value, int lim)
{
int l = i, r = lim + 1;
while (l + 1 < r)
{
int m = (l + r) >> 1;
if (tr.Query(i, m) > value)
r = m;
else
l = m;
}
return l;
}
int SmallRight(SegmentTreeMin &tr, int i, int value, int lim)
{
int l = i, r = lim + 1;
while (l + 1 < r)
{
int m = (l + r) >> 1;
if (tr.Query(i, m) < value)
r = m;
else
l = m;
}
return l;
}
std::vector<int> can_reach(int S)
{
int i = 0;
while (true)
{
int l = BigLeft(hh_max, S, TT[i] - 1) + 1;
int r = BigRight(hh_max, S, TT[i] - 1, M) - 1;
int min = hh_min.Query(l, r + 1);
int limi = SmallRight(tt_min, i, min + 1, N);
int max = tt_max.Query(i, limi);
if (max == TT[i])
return {max, l, r};
i = BigRight(tt_max, i, max - 1, N);
}
}
bool can_reach(int L, int R, int S, int D)
{
std::vector<int> s_reach = can_reach(S);
std::vector<int> d_reach = can_reach(D);
return s_reach[0] == d_reach[0] && s_reach[1] == d_reach[1];
}
