#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
const long long N=200000000009;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[200009],K,pas,L,R,D,seg[800009],l,r,z,za,PI,bo[200009],VAL[200009];
vector <pair <long long, long long> > ANS;
multiset <long long> s;
multiset <long long>::iterator it,tt;
multiset <pair <long long, long long> > S;
multiset <pair <long long, long long> >::iterator IT,TT;
pair <long long, long long> P[200009];
void read(long long q, long long w, long long rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=max(z,seg[rr]);
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void UPD(long long i){
long long D;
multiset <long long>::iterator it,tt;
multiset <pair <long long, long long> >::iterator IT,TT;
tt=s.lower_bound(i);
tt++;
if(tt==s.end()){
R=a+1;
}else{
R=(*tt);
}
it=s.lower_bound(i);
if(it==s.begin()){
L=0;
}else{
it--;
L=(*it);
}
L++;R--;
z=0;
l=i+1;r=R;
if(l<=r) read(1,za,1);
if(r==a) z=N;
e=z;
z=0;
l=L;r=i-1;
if(l<=r) read(1,za,1);
if(l==1) z=N;
e=min(e,z);
S.erase({VAL[i],i});
S.insert({e-f[i]+1,i});
}
void init(long long NN, std::vector<long long> HH) {
a=NN;
for(i=1; i<=a; i++){
f[i]=HH[i-1];
}
za=1;
while(za<a) za*=2;
for(i=1; i<=a; i++){
seg[za+i-1]=f[i];
}
for(i=za-1; i>=1; i--){
seg[i]=max(seg[i*2],seg[i*2+1]);
}
for(i=1; i<=a; i++){
PI++;P[PI]={f[i],i};
}
sort(P+1,P+PI+1);
D=1;
for(ii=1; ii<=PI; ii++){
i=P[ii].second;
tt=s.lower_bound(i);
if(tt==s.end()){
R=a+1;
}else{
R=(*tt);
}
it=s.lower_bound(i);
if(it==s.begin()){
L=0;
}else{
it--;
L=(*it);
}
L++;R--;
e=0;
z=0;
l=i+1;r=R;
if(l<=r) read(1,za,1);
if(r==a) z=N;
if(z<f[i]+D){
e++;
}
z=0;
l=L;r=i-1;
if(l<=r) read(1,za,1);
if(l==1) z=N;
if(z<f[i]+D){
e++;
}
if(e>0) continue;
s.insert(i);bo[i]=1;
}
ANS.push_back({1,s.size()});
//cout<<s.size()<<"\n";
for(i=1; i<=a; i++){
if(bo[i]==0) continue;
tt=s.lower_bound(i);
tt++;
if(tt==s.end()){
R=a+1;
}else{
R=(*tt);
}
it=s.lower_bound(i);
if(it==s.begin()){
L=0;
}else{
it--;
L=(*it);
}
L++;R--;
z=0;
l=i+1;r=R;
if(l<=r) read(1,za,1);
if(r==a) z=N;
e=z;
z=0;
l=L;r=i-1;
if(l<=r) read(1,za,1);
if(l==1) z=N;
e=min(e,z);
S.insert({e-f[i]+1,i});
VAL[i]=e-f[i]+1;
}
/*for(i=1; i<=a; i++){
if(bo[i]==0) continue;
cout<<i<<" "<<VAL[i]<<"\n";
}*/
while(s.size()>1){
IT=S.begin();
D=(*IT).first;
i=(*IT).second;
S.erase(IT);
s.erase(i);
tt=s.lower_bound(i);
if(tt!=s.end()){
UPD((*tt));
}
it=tt;
if(it!=s.begin()){
it--;
UPD((*it));
}
IT=S.begin();
if((*IT).first>D){
ANS.push_back({D,s.size()});
}
}
}
int max_towers(int LL, int RR, int DD) {
pas=1;LL++;RR++;
L=LL;R=RR;D=DD;
c=lower_bound(ANS.begin(),ANS.end(),make_pair(D+1,0LL))-ANS.begin();
c--;
pas=ANS[c].second;
return pas;
}
Compilation message
towers.cpp: In function 'void UPD(long long int)':
towers.cpp:22:15: warning: unused variable 'D' [-Wunused-variable]
22 | long long D;
| ^
/usr/bin/ld: /tmp/cc95Nl1F.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
