#include "obstacles.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
constexpr int clog2(int n) { return ((n < 2) ? 1 : 1 + clog2(n / 2)); }
class SegmentTree
{
public:
SegmentTree() = default;
void init(const vector<int>& raw_)
{
raw = raw_;
n = (int)raw.size();
int sz = (1 << (clog2(n) + 1));
data.resize(sz);
_init(raw, 1, 0, n - 1);
}
int update(int idx, const int& newVal) { raw[idx] = newVal; return _update(1, 0, n - 1, idx, newVal); }
int query(int left, int right) { return _query(1, 0, n - 1, left, right); }
private:
vector<int> raw;
vector<int> data;
int n;
int merge(int l, int r) { return max(l, r); }
int _init(const vector<int>& raw, int node, int start, int end)
{
int mid = (start + end) / 2;
if (start == end)
return data[node] = raw[start];
else
return data[node] = merge(_init(raw, node * 2, start, mid),
_init(raw, node * 2 + 1, mid + 1, end));
}
int _update(int node, int start, int end, int index, const int& newVal)
{
if (index < start || index > end)
return data[node];
if (start == end)
data[node] = newVal;
else
{
int mid = (start + end) / 2;
data[node] = merge(_update(node * 2, start, mid, index, newVal),
_update(node * 2 + 1, mid + 1, end, index, newVal));
}
return data[node];
}
int _query(int node, int start, int end, int left, int right)
{
if (left <= start && end <= right)
return data[node];
int mid = (start + end) / 2;
if (mid < left)
return _query(node * 2 + 1, mid + 1, end, left, right);
if (mid + 1 > right)
return _query(node * 2, start, mid, left, right);
return merge(_query(node * 2, start, mid, left, right),
_query(node * 2 + 1, mid + 1, end, left, right));
}
};
vector<int> t, h;
vector<int> tmin;
vector<int> tmax;
SegmentTree mtmax;
vector<int> ot, mt; // ot = 잠기는 시점, mt = 이동 가능하게 되는 첫 시점
bool can_reach(int l, int r, int s, int d)
{
int target = min(ot[s] - 1, ot[d] - 1);
int sl = s, sr = s;
int dl = d, dr = d;
int lo = 0, hi = s;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
auto v = mtmax.query(mid, s);
if (v > target)
{
lo = mid + 1;
}
else
{
sl = mid;
hi = mid - 1;
}
}
lo = 0; hi = d;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
auto v = mtmax.query(mid, d);
if (v > target)
{
lo = mid + 1;
}
else
{
dl = mid;
hi = mid - 1;
}
}
lo = s; hi = h.size() - 1;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
auto v = mtmax.query(s, mid);
if (v > target)
{
hi = mid - 1;
}
else
{
sr = mid;
lo = mid + 1;
}
}
lo = d; hi = h.size() - 1;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
auto v = mtmax.query(d, mid);
if (v > target)
{
hi = mid - 1;
}
else
{
dr = mid;
lo = mid + 1;
}
}
int lv = max(sl, dl);
int rv = min(sr, dr);
return lv <= rv;
}
int par[200005];
vector<int> hsort[200005];
int find(int x)
{
if (x == par[x])
return x;
return par[x] = find(par[x]);
}
void merge(int x, int y)
{
x = find(x);
y = find(y);
par[x] = y;
ot[y] = max(ot[y], ot[x]);
}
void initialize(vector<int> T, vector<int> H)
{
t = T;
tmin = T;
tmax = T;
for (int i = 1; i < T.size(); i++)
tmin[i] = min(tmin[i - 1], t[i]);
tmin.push_back(-1);
for (int i = 1; i < T.size(); i++)
tmax[i] = max(tmax[i - 1], t[i]);
tmax.push_back(1987654321);
h = H;
ot.resize(h.size());
mt.resize(h.size());
for (int i = 0; i < h.size(); i++)
{
int lo = 0, hi = t.size();
while (lo <= hi)
{
int mid = (lo + hi) / 2;
if (tmin[mid] <= h[i])
{
ot[i] = mid;
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
hsort[ot[i]].push_back(i);
}
for (int i = 0; i < h.size(); i++)
{
int lo = 0, hi = t.size();
while (lo <= hi)
{
int mid = (lo + hi) / 2;
if (tmax[mid] > h[i])
{
mt[i] = mid;
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
}
for (int i = 0; i < h.size(); i++)
par[i] = i;
for (int i = t.size(); i >= 0; i--)
{
for (auto& hi : hsort[i])
{
if (hi > 0 && ot[hi] > mt[hi - 1] && ot[hi - 1] > ot[hi])
merge(hi, hi - 1);
if (hi + 1 < h.size() && ot[hi] > mt[hi + 1] && ot[hi + 1] > ot[hi])
merge(hi, hi + 1);
}
for (auto& hi : hsort[i])
ot[hi] = ot[find(hi)];
}
mtmax.init(mt);
}
