#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e5 + 10;
const int lg = 20;
int n, x, h[maxn], mx[lg][maxn], l[maxn], r[maxn], f[2][maxn];
void add(int *f, int idx, int x){
for (; idx <= n; idx += idx & -idx) f[idx] += x;
}
void add(int *f, int l, int r, int x){
add(f, l, x);
add(f, r+1, -x);
}
int get(int *f, int idx){
int res = 0;
for (; idx; idx -= idx & -idx) res += f[idx];
return res;
}
int get(int *f, int l, int r){
if (r < l) return 0;
return get(f, r) - get(f, l-1);
}
int getmax(int l, int r){
r++;
int x = 31 - __builtin_clz(r-l);
return max(mx[x][l], mx[x][r-(1 << x)]);
}
void init(int N, std::vector<int> H) {
n = N;
for (int i = 0; i < n; i++){
h[i] = H[i];
mx[0][i] = h[i];
}
for (int i = 1; i < lg; i++){
for (int j = 0; j + (1 << i) <= n; j++){
mx[i][j] = max(mx[i-1][j], mx[i-1][j+(1<<(i-1))]);
}
}
for (int i = 1; i + 1 < n; i++){
if (h[i-1] < h[i] && h[i] > h[i+1]) x = i;
}
}
int max_towers(int L, int R, int D) {
memset(f, 0, sizeof f);
vector<int> tmp = {L, R};
if (L < x && x < R) tmp.push_back();
for (auto i: tmp){
int lo = L, hi = i;
while(lo + 1 < hi){
int mid = (lo + hi) >> 1;
if (getmax(mid, i-1) - D >= h[i]) lo = mid;
else hi = mid;
}
l[i] = lo;
}
vector<pii> val;
for (auto i: tmp){
int lo = i, hi = R;
while(lo + 1 < hi){
int mid = (lo + hi) >> 1;
if (getmax(i+1, mid) - D >= h[i]) hi = mid;
else lo = mid;
}
r[i] = hi;
val.push_back({h[i], i});
}
sort(all(val));
int ans = 0;
for (auto [x, y]: val){
if (get(f[0], y+1)) continue;
if (get(f[1], l[y]+1, r[y]+1)) continue;
ans++;
add(f[0], l[y]+1, r[y]+1, 1);
add(f[1], y+1, 1);
}
return ans;
}
Compilation message
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:73:36: error: no matching function for call to 'std::vector<int>::push_back()'
73 | if (L < x && x < R) tmp.push_back();
| ^
In file included from /usr/include/c++/10/vector:67,
from towers.h:1,
from towers.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
1187 | push_back(const value_type& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate expects 1 argument, 0 provided
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
1203 | push_back(value_type&& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate expects 1 argument, 0 provided
