#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "towers.h"
struct Segtree { // point upd, range max
int sz;
vi vals;
Segtree(int N) {
sz = 1;
while (sz < N)
sz *= 2;
vals = vi(2 * sz, 0);
}
void upd(int pos, int val, int id, int left, int right) {
if (right - left == 1) {
vals[id] = val;
return;
}
int mid = (left + right) / 2;
if (pos < mid)
upd(pos, val, 2 * id + 1, left, mid);
else
upd(pos, val, 2 * id + 2, mid, right);
vals[id] = max(vals[2 * id + 1], vals[2 * id + 2]);
}
void upd(int pos, int val) {
upd(pos, val, 0, 0, sz);
}
int query(int qleft, int qright, int id, int left, int right) {
if (qright <= left || right <= qleft)
return 0;
if (qleft <= left && right <= qright)
return vals[id];
int mid = (left + right) / 2;
int s1 = query(qleft, qright, 2 * id + 1, left, mid);
int s2 = query(qleft, qright, 2 * id + 2, mid, right);
return max(s1, s2);
}
int query(int qleft, int qright) {
return query(qleft, qright, 0, 0, sz);
}
};
int N;
vi H;
int maxv = -1;
int maxp = -1;
void init(int N_g, vi H_g) {
N = N_g;
H = H_g;
}
int max_towers(int L, int R, int D) {
int K = R - L + 1;
vi h;
for (int j = L; j <= R; j++) {
h.pb(H[j]);
}
/* cout<<"h: ";
for (int x : h)
cout<<x<<" ";
cout<<endl;*/
Segtree st(K);
for (int j = 0; j < K; j++) {
st.upd(j, h[j]);
}
vector<ii> allp; // {height, pos}
for (int j = 0; j < K; j++) {
allp.pb({h[j], j});
}
sort(allp.begin(), allp.end());
vi order;
for (int j = 0; j < K; j++) {
order.pb(allp[j].se);
}
int total = 0;
vector<bool> used(K, false);
for (int j = 0; j < K; j++) { // see if can use order[j]
// cout<<"at "<<j<<endl;
bool can = true;
for (int k = 0; k < K; k++) {
if (k == order[j])
continue;
if (used[k]) {
int maxr = 0; // max between k and order[j]
if (k < order[j])
maxr = st.query(k + 1, order[j]);
else
maxr = st.query(order[j] + 1, k);
// cout<<k<<", "<<order[j]<<": "<<maxr<<endl;
if (h[order[j]] > maxr - D || h[k] > maxr - D)
can = false;
}
}
if (can) {
// cout<<"can use "<<order[j]<<endl;
total++;
used[order[j]] = true;
}
}
/* cout<<"used: ";
for (bool b : used)
cout<<b<<" ";
cout<<endl;*/
return total;
}
// shortest to tallest, greedy (?)
// just code it up to see if it works
