#include<bits/stdc++.h>
#include"holiday.h"
#define MAXN 500007
using namespace std;
int n,a[MAXN],start;
vector<int> w;
unordered_map<int,int> mp;
int ret[MAXN],cnt;
long long ans;
struct ST{
pair<long long,int> tree[4*MAXN];
void init(){
for(int i=1;i<=4*cnt;i++){
tree[i]={0,0};
}
}
pair<long long,int> combine(pair<long long,int> fr,pair<long long,int> sc){
return {fr.first+sc.first,fr.second+sc.second};
}
void update(int v,int l,int r,int pos,int val){
if(l==r){
tree[v].second+=val;
tree[v].first+=ret[l]*val;
}else{
int tt=(l+r)/2;
if(pos<=tt)update(2*v,l,tt,pos,val);
else update(2*v+1,tt+1,r,pos,val);
tree[v]=combine(tree[2*v],tree[2*v+1]);
}
}
long long getsum(int v,int l,int r,long long k){
if(k<0)return 0;
if(l==r){
if(tree[v].second<=k)return tree[v].first;
return k*ret[l];
}else{
int tt=(l+r)/2;
if(tree[2*v+1].second>=k){
return getsum(2*v+1,tt+1,r,k);
}else{
return getsum(2*v,l,tt,k-tree[2*v+1].second) + tree[2*v+1].first;
}
}
}
}seg;
long long pref[MAXN],suff[MAXN];
void solveopt_right(int dl,int dr,int optl,int optr){
if(dl>dr)return;
int mid=(dl+dr)/2,opt;
suff[mid]=0;
for(int i=optl;i<=optr;i++){
seg.update(1,1,cnt,a[i],1);
long long curr=seg.getsum(1,1,cnt,mid-(i-start));
if(curr>=suff[mid]){
suff[mid]=curr;
opt=i;
}
}
if(suff[mid]==0)opt=optl;
for(int i=optl;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
solveopt_right(dl,mid-1,optl,min(optr,opt+1));
for(int i=optl;i<max(opt-1,optl);i++)seg.update(1,1,cnt,a[i],1);
solveopt_right(mid+1,dr,max(opt-1,optl),optr);
for(int i=optl;i<max(opt-1,optl);i++)seg.update(1,1,cnt,a[i],-1);
}
void solveopt_left(int dl,int dr,int optl,int optr){
if(dl>dr)return;
int mid=(dl+dr)/2,opt;
pref[mid]=0;
for(int i=optr;i>=optl;i--){
seg.update(1,1,cnt,a[i],1);
long long curr=seg.getsum(1,1,cnt,mid-2*(start-1-i));
if(curr>=pref[mid]){
pref[mid]=curr;
opt=i;
}
}
if(pref[mid]==0)opt=optr;
for(int i=optl;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
solveopt_left(dl,mid-1,max(opt-1,optl),optr);
for(int i=min(optrl,opt+1)+1;i<=optr;i++)seg.update(1,1,cnt,a[i],1);
solveopt_left(mid+1,dr,optl,min(optr,opt+1));
for(int i=min(optrl,opt+1)+1;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
}
long long int findMaxAttraction(int N, int st, int d, int attraction[]) {
//long long int findMaxAttraction(int N, int st, int d, vector<int> attraction) {
n=N; start=st+1;
for(int i=1;i<=n;i++){
a[i]=attraction[i-1];
w.push_back(a[i]);
}
sort(w.begin(),w.end());
for(int i=0;i<w.size();i++){
if(i==0 or w[i]!=w[i-1])cnt++;
mp[w[i]]=cnt; ret[cnt]=w[i];
}
for(int i=1;i<=n;i++)a[i]=mp[a[i]];
seg.init();
solveopt_right(0,d,start,n);
seg.init();
solveopt_left(0,d,1,start-1);
ans=max(ans,suff[d]);
for(int i=0;i<=d-2;i++){
ans=max(ans,pref[i]+suff[d-2-i]);
}
reverse(a+1,a+n+1);
start=n-start+1;
seg.init();
solveopt_right(0,d,start,n);
seg.init();
solveopt_left(0,d,1,start-1);
ans=max(ans,suff[d]);
for(int i=0;i<=d-2;i++){
ans=max(ans,pref[i]+suff[d-2-i]);
}
return ans;
}
/*int main(){
cout<<findMaxAttraction(5,2,7,{10,2,20,30,1})<<"\n";
return 0;
}*/
Compilation message
holiday.cpp: In function 'void solveopt_left(int, int, int, int)':
holiday.cpp:111:16: error: 'optrl' was not declared in this scope; did you mean 'optl'?
111 | for(int i=min(optrl,opt+1)+1;i<=optr;i++)seg.update(1,1,cnt,a[i],1);
| ^~~~~
| optl
holiday.cpp:114:16: error: 'optrl' was not declared in this scope; did you mean 'optl'?
114 | for(int i=min(optrl,opt+1)+1;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
| ^~~~~
| optl
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:127:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i=0;i<w.size();i++){
| ~^~~~~~~~~
