#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long inf=1e16;
int n,h[MAXN],maxh,num,delta,from[MAXN],to[MAXN],border,maxdelta[MAXN];
int dp[MAXN],ans,pref[MAXN],se,te;
pair<int,int> tree[4*MAXN];
int mins[4*MAXN];
pair<int,int> combine(pair<int,int> fr,pair<int,int> sc){
if(fr.first>sc.first)return fr;
return sc;
}
void build(int v,int l,int r){
if(l==r){
tree[v]={h[l],l};
mins[v]=h[l];
}else{
int tt=(l+r)/2;
build(2*v,l,tt);
build(2*v+1,tt+1,r);
tree[v]=combine(tree[2*v],tree[2*v+1]);
mins[v]=min(mins[2*v],mins[2*v+1]);
}
}
pair<int,int> best(int v,int l,int r,int ll,int rr){
if(ll>rr)return {-1,0};
if(l==ll and r==rr){
return tree[v];
}else{
int tt=(l+r)/2;
return combine( best(2*v,l,tt,ll,min(tt,rr)) , best(2*v+1,tt+1,r,max(tt+1,ll),rr) );
}
}
int minh(int v,int l,int r,int ll,int rr){
if(ll>rr)return 1000000000;
if(l==ll and r==rr){
return mins[v];
}else{
int tt=(l+r)/2;
return min( minh(2*v,l,tt,ll,min(tt,rr)) , minh(2*v+1,tt+1,r,max(tt+1,ll),rr) );
}
}
vector<int> st,poss,lt,rt;
void calc(){
for(int i=1;i<=n;i++){
while(!st.empty() and h[i]>h[st.back()]){
st.pop_back();
}
st.push_back(i);
int l=-1,r=st.size(),tt;
while(l+1<r){
tt=(l+r)/2;
if(h[st[tt]]>=h[i]+delta){
l=tt;
}else{
r=tt;
}
}
if(l!=-1 and minh(1,0,n+1,st[l],i)>=h[i])from[i]=st[l];
else from[i]=0;
}
while(!st.empty())st.pop_back();
for(int i=n;i>=1;i--){
while(!st.empty() and h[i]>h[st.back()]){
st.pop_back();
}
st.push_back(i);
int l=-1,r=st.size(),tt;
while(l+1<r){
tt=(l+r)/2;
if(h[st[tt]]>=h[i]+delta){
l=tt;
}else{
r=tt;
}
}
if(l!=-1 and minh(1,0,n+1,i,st[l])>=h[i])to[i]=st[l];
else to[i]=n+1;
}
for(int i=1;i<=n;i++){
if(from[i]>=1 and to[i]<=n){
poss.push_back(i);
}
if(to[i]<=n)lt.push_back(i);
if(from[i]>=1)rt.push_back(i);
}
}
void calc2(){
for(int i=1;i<=n;i++)maxdelta[i]=inf;
for(int i=0;i<=n;i++){
while(!st.empty() and h[i]>h[st.back()]){
st.pop_back();
}
st.push_back(i);
int l=-1,r=st.size(),tt;
while(l+1<r){
tt=(l+r)/2;
if(minh(1,0,n+1,st[tt],i)>=h[i]){
r=tt;
}else{
l=tt;
}
}
maxdelta[i]=min(maxdelta[i],h[st[r]]-h[i]);
}
while(!st.empty())st.pop_back();
for(int i=n+1;i>=1;i--){
while(!st.empty() and h[i]>h[st.back()]){
st.pop_back();
}
st.push_back(i);
int l=-1,r=st.size(),tt;
while(l+1<r){
tt=(l+r)/2;
if(minh(1,0,n+1,i,st[tt])>=h[i]){
r=tt;
}else{
l=tt;
}
}
maxdelta[i]=min(maxdelta[i],h[st[r]]-h[i]);
}
while(!st.empty())st.pop_back();
sort(maxdelta+1,maxdelta+n+1);
}
void init(int N,vector<int> H){
n=N;
for(int i=1;i<=n;i++){
h[i]=H[i-1];
}
h[0]=h[n+1]=1000000000;
build(1,0,n+1);
calc2();
}
int solve(int l,int r,int maxh,int d){
if(l>r)return 0;
int pos=best(1,0,n+1,l,r).second;
int z=0;
if(minh(1,0,n+1,l,r)<=maxh)z=1;
return max(z, solve(l,pos-1,h[pos]-d,d)+solve(pos+1,r,h[pos]-d,d) );
}
int max_towers(int L, int R, int D){
if(delta==0){
delta=D;
calc();
}
L++; R++;
if(D==delta){
ans=0;
int l=-1,r=poss.size(),tt;
while(l+1<r){
tt=(l+r)/2;
if(from[poss[tt]]>=L){
r=tt;
}else{
l=tt;
}
}
se=r;
l=-1; r=poss.size();
while(l+1<r){
tt=(l+r)/2;
if(to[poss[tt]]<=R){
l=tt;
}else{
r=tt;
}
}
te=l;
if(se<=te)ans+=te-se+1;
if(se==poss.size())se=R+1;
else se=poss[se];
if(te==-1)te=L-1;
else te=poss[te];
l=-1; r=lt.size();
while(l+1<r){
tt=(l+r)/2;
if(lt[tt]>=L){
r=tt;
}else{
l=tt;
}
}
border=-1;
if(r!=lt.size() and to[lt[r]]<se){
border=to[lt[r]]; ans++;
}
l=-1; r=rt.size();
while(l+1<r){
tt=(l+r)/2;
if(rt[tt]<=R){
l=tt;
}else{
r=tt;
}
}
if(l!=-1 and from[rt[l]]>=max(border,te+1))ans++;
if(ans==0)ans++;
return ans;
}
if(L==1 and R==n){
int l=0,r=n+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(maxdelta[tt]>=D){
r=tt;
}else{
l=tt;
}
}
return n-r+1;
}
return solve(L,R,1000000000,D);
}
int main(){
init(7, {10, 20, 60, 40, 50, 30, 70});
cout<<max_towers(1,5,10)<<"\n";
cout<<max_towers(0, 6, 17)<<"\n";
}
Compilation message
towers.cpp: In function 'void calc2()':
towers.cpp:105:38: warning: overflow in conversion from 'long long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
105 | for(int i=1;i<=n;i++)maxdelta[i]=inf;
| ^~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:207:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | if(se==poss.size())se=R+1;
| ~~^~~~~~~~~~~~~
towers.cpp:224:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
224 | if(r!=lt.size() and to[lt[r]]<se){
| ~^~~~~~~~~~~
/usr/bin/ld: /tmp/ccDuteHM.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccg5bibM.o:towers.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
