#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> t,h;
int maxl[200005];
int maxpref[200005];
void initialize(std::vector<int> T, std::vector<int> H)
{
t = T;
h = H;
maxpref[0] = t[0];
for(int i=1;i<t.size();i++)
maxpref[i] = max(maxpref[i-1], t[i]);
priority_queue<pair<int,int>> pq;
for(int i=0;i<h.size();i++)
{
maxl[i] = 0;
while(maxl[i] + 1 < t.size() && t[maxl[i]+1] > h[i])
maxl[i]++;
maxl[i] = maxpref[maxl[i]];
pq.push({maxl[i], i});
}
while(!pq.empty())
{
auto [cval,i] = pq.top();
pq.pop();
if(maxl[i] != cval)
continue;
for(int v:{i-1,i+1})
{
if(0 <= v && v < h.size() && maxl[v] < maxl[i] && h[v] < maxl[i])
{
maxl[v] = maxl[i];
pq.push({maxl[v], v});
}
}
}
}
bool can_reach(int L, int R, int S, int D)
{
int maxh = 0;
for(int i=L;i<=R;i++)
maxh = max(maxh, h[i]);
return (maxl[L] >= maxh && maxl[R] >= maxh);
}
