#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> h;
int n;
vector<vector<int>> adj;
vector<int> tree;
vector<int> Tree;
int nN = 0;
void init(int N, std::vector<int> H)
{
n = N;
h = H;
adj.assign(n , {});
while(__builtin_popcount(N) != 1)
{
N++;
h.push_back(0);
}
tree.assign(2 * N , 0);
for(int i = 0 ; i < N ; i++)
{
tree[i + N] = h[i];
}
Tree = tree;
for(int i = N - 1 ; i >= 1 ; i--)
{
tree[i] = max(tree[i<<1] , tree[i<<1|1]);
Tree[i] = min(Tree[i<<1] , Tree[i<<1|1]);
}
nN = N;
}
int walkgr(int node , int s , int e , int i , int x)
{
if(i > e)
return -1;
if(tree[node] < x)
return -1;
if(s == e)
return e;
int md = (s + e)>>1;
int lt = walkgr(node<<1 , s , md , i , x);
if(lt == -1)
return walkgr(node<<1|1 , md + 1 , e , i , x);
else
return lt;
}
int fr_greater_than(int i , int x)
{
return walkgr(1 , 0 , nN - 1, i , x);
}
int walkle(int node , int s , int e , int i , int x)
{
if(i > e)
return -1;
if(Tree[node] > x)
return -1;
if(s == e)
return e;
int md = (s + e)>>1;
int lt = walkle(node<<1 , s , md , i , x);
if(lt == -1)
return walkle(node<<1|1 , md + 1 , e , i , x);
else
return lt;
}
int fr_less_than(int i , int x)
{
return walkle(1 , 0 , nN - 1, i , x);
}
int walkgr0(int node , int s , int e , int i , int x)
{
if(i < s)
return -1;
if(tree[node] < x)
return -1;
if(s == e)
return e;
int md = (s + e)>>1;
int lt = walkgr0(node<<1|1 , md + 1 , e , i , x);
if(lt == -1)
return walkgr0(node<<1 , s , md , i , x);
else
return lt;
}
int lst_greater_than(int i , int x)
{
return walkgr0(1 , 0 , nN - 1, i , x);
}
int walkle0(int node , int s , int e , int i , int x)
{
if(i < s)
return -1;
if(Tree[node] > x)
return -1;
if(s == e)
return e;
int md = (s + e)>>1;
int lt = walkle0(node<<1|1 , md + 1 , e , i , x);
if(lt == -1)
return walkle0(node<<1 , s , md , i , x);
else
return lt;
}
int lst_less_than(int i , int x)
{
return walkle0(1 , 0 , nN - 1, i , x);
}
int max_towers(int L, int R, int D)
{
vector<int> nxt(n , n);
for(int i = 0 ; i < n ; i++)
{
int k = fr_greater_than(i , h[i] + D);
// cout<<i<<" : "<<k<<'\n';
if(k == -1)
continue;
int j = fr_less_than(k , h[i]);
if(j == -1)
continue;
nxt[i] = j;
}
for(int i = 0 ; i < n ; i++)
{
int k = lst_greater_than(i , h[i] + D);
// cout<<i<<" : "<<k<<'\n';
if(k == -1)
continue;
int j = lst_less_than(k , h[i]);
// cout<<i<<" : "<<j<<'\n';
if(j == -1)
continue;
nxt[j] = min(nxt[j] , i);
}
// for(int i = 0 ; i <n ; i++)
// cout<<nxt[i]<<'\n';
vector<int> dp(n+1,0);
for(int i = R ; i >= L ; i--)
{
dp[i] = dp[nxt[i]] + 1;
dp[i] = max(dp[i] , dp[i + 1]);
}
return dp[L];
}
