#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll big = 1000000007;
const int MAXN = 100001;
int n;
vi H2;
struct Segtree {
Segtree *l = 0, *r = 0;
int lo, hi, ma = -big, mi = big, ab = 0, ba = 0;
Segtree(vi& v, int lo, int hi) : lo(lo), hi(hi) {
if (lo + 1 < hi) {
int mid = lo + (hi - lo)/2;
l = new Segtree(v, lo, mid); r = new Segtree(v, mid, hi);
ma = max(l->ma, r->ma);
mi = min(l->mi, r->mi);
ab = max(l->ab, r->ab);
ab = max(ab, (r->ma) - (l->mi));
ba = max(l->ba, r->ba);
ba = max(ba, (l->ma) - (r->mi));
}
else{
ma = v[lo];
mi = v[lo];
}
}
int get_max(int L, int R) {
if (R <= lo || hi <= L) return -big;
if (L <= lo && hi <= R) return ma;
return max(l->get_max(L, R), r->get_max(L, R));
}
int get_min(int L, int R) {
if (R <= lo || hi <= L) return big;
if (L <= lo && hi <= R) return mi;
return min(l->get_min(L, R), r->get_min(L, R));
}
int get_ab(int L, int R){
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) return ab;
int res = max(l->get_ab(L, R), r->get_ab(L, R));
int x = l->get_min(L,R);
int y = r->get_max(L,R);
return max(res,y-x);
}
int get_ba(int L, int R){
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) return ba;
int res = max(l->get_ba(L, R), r->get_ba(L, R));
int x = r->get_min(L,R);
int y = l->get_max(L,R);
return max(res,y-x);
}
};
Segtree *ST;
map<int,int> HI;
int delta[MAXN] = {0};
vi ind;
void get_ct(int L, int R){
if(L >= R)return;
if(L == R-1){
delta[L] = 0;
return;
}
int i = HI[ST->get_max(L, R)];
int x = ST->get_min(L,i);
int y = ST->get_min(i+1,R);
delta[i] = H2[i]-max(x, y);
delta[i] = max(delta[i], 0);
get_ct(L, i);
get_ct(i+1,R);
}
bool comp(int i, int j){
return delta[i] > delta[j];
}
void init(int N, int* H){
n = N;
rep(c1,0,n){
H2.push_back(H[c1]);
HI[H[c1]] = c1;
ind.push_back(c1);
}
ST = new Segtree(H2, 0, n);
get_ct(0, n);
sort(all(ind), comp);
}
int max_towers(int L, int R, int D){
int lo = 0;
int hi = n;
if(delta[ind[0]] < D)return 1;
while(lo < hi-1){
int mid = (lo+hi)/2;
if(delta[ind[mid]] < D){
hi = mid;
}
else{
lo = mid;
}
}
return hi + 1;
}
/*
int main() {
int N;
N = 7;
int H[7] = {1,4,2,9,3,6,5};
init(N,H);
cout << max_towers(0, 7, 1) << "\n";
cout << max_towers(0, 7, 2) << "\n";
cout << max_towers(0, 7, 3) << "\n";
cout << max_towers(0, 7, 4) << "\n";
return 0;
}
*/
Compilation message
/usr/bin/ld: /tmp/ccREZyhC.o: in function `main':
stub.cpp:(.text.startup+0x179): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
