#include "obstacles.h"
#include <algorithm>
#include <climits>
#include <stack>
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;
}
};
SegmentTreeMax hh_max;
int p[200001];
int GP(int i)
{
if (i == p[i])
return i;
return p[i] = GP(p[i]);
}
void initialize(std::vector<int> T, std::vector<int> H)
{
hh_max = SegmentTreeMax(H);
std::vector<std::pair<int, int>> tt;
tt.push_back(std::make_pair(T[0], T[0]));
for (int i = 1, min = T[0]; i < T.size(); i++)
{
if (T[i] < min)
min = T[i];
if (T[i] > tt.back().first)
{
if (min == tt.back().second)
{
tt.back().first = T[i];
}
else
{
tt.push_back(std::make_pair(T[i], min));
}
}
}
for (int i = 0; i < H.size(); i++)
{
p[i] = i;
}
std::stack<std::pair<int, int>> st;
for (int i = 0; i < H.size(); i++)
{
while (st.size() > 0 && st.top().first > H[i])
{
st.pop();
}
if (st.size() > 0)
{
int j = st.top().second;
int pi = GP(i);
int pj = GP(j);
if (pi != pj)
{
int max = hh_max.Query(j, i + 1);
int l = -1, r = tt.size();
while (l + 1 < r)
{
int m = (l + r) >> 1;
if (tt[m].first > max)
r = m;
else
l = m;
}
if (r < tt.size() && tt[r].second > H[i])
{
p[pi] = pj;
}
}
}
st.push(std::make_pair(H[i], i));
}
while (st.size() > 0)
st.pop();
for (int i = H.size() - 1; i >= 0; i--)
{
while (st.size() > 0 && st.top().first > H[i])
{
st.pop();
}
if (st.size() > 0)
{
int j = st.top().second;
int pi = GP(i);
int pj = GP(j);
if (pi != pj)
{
int max = hh_max.Query(i, j + 1);
int l = -1, r = tt.size();
while (l + 1 < r)
{
int m = (l + r) >> 1;
if (tt[m].first > max)
r = m;
else
l = m;
}
if (r < tt.size() && tt[r].second > H[i])
{
p[pi] = pj;
}
}
}
}
}
bool can_reach(int L, int R, int S, int D)
{
int s = GP(S);
int d = GP(D);
return s == d;
}
