#include "towers.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<int> H;
int N;
class segTree{
public:
int lef_ind;
int rig_ind;
int min_val;
int max_val;
segTree* lef_child;
segTree* rig_child;
segTree(int l, int r)
{
lef_ind = l;
rig_ind = r;
min_val = 500'000;
max_val = -1;
if (l!=r)
{
int mid = (l+r)/2;
lef_child = &segTree(l, mid);
rig_child = &segTree(mid+1, r);
}
else
{
lef_child = nullptr;
rig_child = nullptr;
}
};
void update(int ind, int val)
{
if (lef_child == nullptr)
{
min_val = min(min_val, val);
max_val = max(max_val, val);
}
else
{
int mid = (lef_ind+rig_ind)/2;
if (ind<=mid)
lef_child->update(ind, val);
else
rig_child->update(ind, val);
min_val = min(lef_child->min_val, rig_child->min_val);
max_val = max(lef_child->max_val, rig_child->max_val);
}
}
int mini(int l, int r)
{
int lef_overlap = max(l, lef_ind);
int rig_overlap = min(r, rig_ind);
if ((lef_ind==lef_overlap) and (rig_ind==rig_overlap))
return min_val;
if (lef_overlap < rig_overlap)
return 500'000;
return min(lef_child->mini(l, r), rig_child->mini(l, r));
}
int maxi(int l, int r)
{
int lef_overlap = max(l, lef_ind);
int rig_overlap = min(r, rig_ind);
if ((lef_ind==lef_overlap) and (rig_ind==rig_overlap))
return max_val;
if (lef_overlap < rig_overlap)
return 0;
return max(lef_child->maxi(l, r), rig_child->maxi(l, r));
}
};
void init(int n, std::vector<int> h) {
H = h;
N = n;
}
int max_towers(int L, int R, int D) {
segTree lo = segTree(1, 100000);
segTree hi = segTree(0, 100000);
lo.update(1, H[L]);
hi.update(0, H[L]);
int ans = 1;
for (int i=L+1; i<=R; i++)
{
//go high
int bin_lo = 1;
int bin_hi = i-L;//perhaps edit to 100'000?
int target = H[i]-D;
if (lo.mini(bin_lo, bin_hi) > target)
{
bin_lo = 0;
bin_hi = 0;
}
while (bin_lo != bin_hi)
{
int bin_mid = (bin_lo + bin_hi + 1)/2;
if (lo.mini(bin_mid, bin_hi) <= target)
bin_lo = bin_mid;
else
bin_hi = bin_mid-1;
}
int ans_one = bin_lo;
//go low
bin_lo = 0;
bin_hi = i-L;//perhaps edit to 100'000?
target = H[i]+D;
if (hi.maxi(bin_lo, bin_hi) < target)
{
bin_lo = 0;
bin_hi = 0;
}
while (bin_lo != bin_hi)
{
int bin_mid = (bin_lo + bin_hi + 1)/2;
if (hi.maxi(bin_mid, bin_hi) >= target)
bin_lo = bin_mid;
else
bin_hi = bin_mid-1;
}
int ans_two = bin_lo+1;
lo.update(ans_two, H[i]);
hi.update(ans_one, H[i]);
ans = max(ans, ans_two);
}
return ans;
}
Compilation message
towers.cpp: In constructor 'segTree::segTree(int, int)':
towers.cpp:27:26: error: taking address of rvalue [-fpermissive]
27 | lef_child = &segTree(l, mid);
| ^~~~~~~~~~~~~~~
towers.cpp:28:26: error: taking address of rvalue [-fpermissive]
28 | rig_child = &segTree(mid+1, r);
| ^~~~~~~~~~~~~~~~~
