#include"towers.h"
#include<vector>
#include<iostream>
using namespace std;
const int TREE_SIZE=1<<17;
int n;
vector<int>arr;
vector<int>thres;
vector<int>prv,nxt;
vector<vector<int>>arr_rmq;
vector<vector<pair<int,int>>>arr_rmq2;
vector<vector<int>>thres_rmq;
void init_prev(){
prv.resize(n);
vector<int>s;
for(int i=0;i<n;i++){
while(s.size()&&arr[s.back()]>arr[i])
s.pop_back();
if(s.empty())
prv[i]=-1;
else
prv[i]=s.back();
s.push_back(i);
}
}
void init_nxt(){
nxt.resize(n);
vector<int>s;
for(int i=n-1;i>=0;i--){
while(s.size()&&arr[s.back()]>arr[i])
s.pop_back();
if(s.empty())
nxt[i]=-1;
else
nxt[i]=s.back();
s.push_back(i);
}
}
void init_arr_rmq(){
arr_rmq=vector<vector<int>>(20,vector<int>(n));
arr_rmq[0]=arr;
for(int p=1;p<20;p++){
for(int i=0;i+(1<<p)<=n;i++){
arr_rmq[p][i]=max(arr_rmq[p-1][i],arr_rmq[p-1][i+(1<<(p-1))]);
}
}
}
int get_arr_max(int l,int r){
int pw2=2;
int p=0;
while(pw2<r-l){
pw2*=2;
p++;
}
pw2/=2;
return max(arr_rmq[p][l],arr_rmq[p][r-pw2]);
}
void init_thres(){
thres.resize(n);
for(int i=0;i<n;i++){
int mn=2e9;
if(prv[i]!=-1){
int mx1=get_arr_max(prv[i],i);
mn=min(mn,mx1);
}
if(nxt[i]!=-1){
int mx2=get_arr_max(i,nxt[i]);
mn=min(mn,mx2);
}
thres[i]=mn-arr[i];
}
}
void init_thres_rmq(){
thres_rmq=vector<vector<int>>(20,vector<int>(n));
thres_rmq[0]=thres;
for(int p=1;p<20;p++){
for(int i=0;i+(1<<p)<=n;i++){
thres_rmq[p][i]=max(thres_rmq[p-1][i],thres_rmq[p-1][i+(1<<(p-1))]);
}
}
}
int get_thres_max(int l,int r){
int pw2=2;
int p=0;
while(pw2<r-l){
pw2*=2;
p++;
}
pw2/=2;
return max(thres_rmq[p][l],thres_rmq[p][r-pw2]);
}
void init_arr_rmq2(){
arr_rmq2=vector<vector<pair<int,int>>>(20,vector<pair<int,int>>(n));
for(int i=0;i<n;i++)
arr_rmq2[0][i]={arr[i],i};
for(int p=1;p<20;p++){
for(int i=0;i+(1<<p)<=n;i++){
arr_rmq2[p][i]=min(arr_rmq2[p-1][i],arr_rmq2[p-1][i+(1<<(p-1))]);
}
}
}
pair<int,int>get_arr_min(int l,int r){
int pw2=2;
int p=0;
while(pw2<r-l){
pw2*=2;
p++;
}
pw2/=2;
return min(arr_rmq2[p][l],arr_rmq2[p][r-pw2]);
}
struct Diff{
vector<int>mn;
vector<int>mx;
vector<int>tree;
Diff():tree(2*TREE_SIZE),mn(2*TREE_SIZE),mx(2*TREE_SIZE){}
void update(int i,int x){
i+=TREE_SIZE;
mn[i]=x;
mx[i]=x;
tree[i]=0;
i/=2;
while(i){
mn[i]=min(mn[2*i],mn[2*i+1]);
mx[i]=max(mx[2*i],mx[2*i+1]);
tree[i]=max(max(tree[2*i],tree[2*i+1]),mx[2*i]-mn[2*i+1]);
i/=2;
}
}
pair<pair<int,int>,int>get(int node,int rl,int rr,int l,int r){
if(r<=rl||rr<=l)
return{{(int)1e9+1,-1},0};
if(l<=rl&&rr<=r)
return{{mn[node],mx[node]},tree[node]};
int mid=(rl+rr)/2;
auto res1=get(2*node,rl,mid,l,r);
auto res2=get(2*node+1,mid,rr,l,r);
int mn1=res1.first.first;
int mx1=res1.first.second;
int r1=res1.second;
int mn2=res2.first.first;
int mx2=res2.first.second;
int r2=res2.second;
int mn=min(mn1,mn2);
int mx=max(mx1,mx2);
int rs=max(max(r1,r2),mx1-mn2);
return{{mn,mx},rs};
}
int get(int l,int r){
return get(1,0,TREE_SIZE,l,r).second;
}
};
Diff diff1,diff2;
struct Node{
int sum;
Node*ch1,*ch2;
Node():sum(0),ch1(nullptr),ch2(nullptr){}
};
int get(Node*node,int rl,int rr,int l,int r){
if(node==nullptr)
return 0;
if(r<=rl||rr<=l)
return 0;
if(l<=rl&&rr<=r)
return node->sum;
int mid=(rl+rr)/2;
return get(node->ch1,rl,mid,l,r)+get(node->ch2,mid,rr,l,r);
}
int get_sum(Node*node){
if(node==nullptr)
return 0;
return node->sum;
}
Node*update(Node*node,int rl,int rr,int i){
if(rl==rr-1){
node=new Node;
node->sum=1;
return node;
}
int mid=(rl+rr)/2;
Node*new_node=new Node;
new_node->ch1=node->ch1;
new_node->ch2=node->ch2;
new_node->ch1=node->ch1;
if(i>=mid){
if(!node->ch2)
node->ch2=new Node;
new_node->ch2=update(node->ch2,mid,rr,i);
}else{
if(!node->ch1)
node->ch1=new Node;
new_node->ch1=update(node->ch1,rl,mid,i);
}
new_node->sum=get_sum(new_node->ch1)+get_sum(new_node->ch2);
return new_node;
}
vector<pair<int,Node*>>trees;
void init_tree(){
vector<pair<int,int>>vec(n);
for(int i=0;i<n;i++)
vec[i]={thres[i],i};
sort(vec.begin(),vec.end());
reverse(vec.begin(),vec.end());
trees.resize(n+1);
Node*root=new Node;
trees[0]={(int)1e9+1,root};
for(int i=0;i<n;i++){
root=update(root,0,TREE_SIZE,vec[i].second);
trees[i+1].first=vec[i].first;
trees[i+1].second=root;
}
}
void init(int N,vector<int>H){
arr=H;
n=(int)arr.size();
init_prev();
init_nxt();
init_arr_rmq();
init_thres();
init_thres_rmq();
init_arr_rmq2();
for(int i=0;i<n;i++){
diff1.update(i,arr[i]);
diff2.update(i,arr[n-i-1]);
}
init_tree();
}
int max_towers(int L,int R,int D){
int res=0;
/*for(int i=L;i<=R;i++){
if(thres[i]>=D){
res++;
}
}*/
{
int l=0,r=n+2;
while(l<r-1){
int mid=(l+r)/2;
if(trees[mid].first>=D)
l=mid;
else
r=mid;
}
res+=get(trees[l].second,0,TREE_SIZE,L,R+1);
}
int first=-1,last=-1;
if(get_thres_max(L,R+1)<D){
first=get_arr_min(L,R+1).second;
last=first;
res=1;
}else{
{
int l=L,r=R+1;
while(l<r-1){
int mid=(l+r)/2;
if(get_thres_max(L,mid)>=D)
r=mid;
else
l=mid;
}
first=l;
}
{
int l=L,r=R+1;
while(l<r-1){
int mid=(l+r)/2;
if(get_thres_max(mid,R+1)>=D)
l=mid;
else
r=mid;
}
last=l;
}
}
if(get_arr_max(L,first)>=arr[first]+D){
int l=L,r=first;
while(l<r-1){
int mid=(l+r)/2;
if(get_arr_max(mid,first)>=arr[first]+D)
l=mid;
else
r=mid;
}
res+=diff2.get(n-l-1,n-L)>=D;
}
if(get_arr_max(last,R+1)>=arr[last]+D){
int l=last,r=R+1;
while(l<r-1){
int mid=(l+r)/2;
if(get_arr_max(last,mid)>=arr[last]+D)
r=mid;
else
l=mid;
}
res+=diff1.get(l,R+1)>=D;
}
return res;
}
Compilation message
towers.cpp: In constructor 'Diff::Diff()':
towers.cpp:130:16: warning: 'Diff::tree' will be initialized after [-Wreorder]
130 | vector<int>tree;
| ^~~~
towers.cpp:128:16: warning: 'std::vector<int> Diff::mn' [-Wreorder]
128 | vector<int>mn;
| ^~
towers.cpp:131:5: warning: when initialized here [-Wreorder]
131 | Diff():tree(2*TREE_SIZE),mn(2*TREE_SIZE),mx(2*TREE_SIZE){}
| ^~~~
towers.cpp: In function 'void init_tree()':
towers.cpp:227:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
227 | sort(vec.begin(),vec.end());
| ^~~~
| qsort
towers.cpp:228:5: error: 'reverse' was not declared in this scope
228 | reverse(vec.begin(),vec.end());
| ^~~~~~~
