#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=optl;
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;
}
}
for(int i=optl;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
solveopt_right(dl,mid-1,optl,opt);
for(int i=optl;i<opt;i++)seg.update(1,1,cnt,a[i],1);
solveopt_right(mid+1,dr,opt,optr);
for(int i=optl;i<opt;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=optr;
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;
}
}
for(int i=optl;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
solveopt_left(dl,mid-1,opt,optr);
for(int i=opt+1;i<=optr;i++)seg.update(1,1,cnt,a[i],1);
solveopt_left(mid+1,dr,optl,opt);
for(int i=opt+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,pref[d]);
if(start==1)return ans;
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,pref[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 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:123:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i=0;i<w.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
14024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
9244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
14012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
