#include"holiday.h"
#include<bits/stdc++.h>
#define II signed
#define int long long
using namespace std;
int valL[250100],valR[250100];
II indd[100100];
pair<II,II> V[100100];
struct node{
int sum;
II cnt;
node *lc,*rc;
node(){lc=rc=0,sum=cnt=0;}
node(int S){cnt=1,sum=V[S-1].first,lc=rc=0;}
node(node*a,node*b){
lc=a,rc=b;
cnt=a->cnt+b->cnt;
sum=a->sum+b->sum;
}
} *RTL[100100],*RTR[100100];
int query(node*x,II need){
if(!x) return 0;
if(x->cnt<=need)
return x->sum;
if(x->rc->cnt>=need)
return query(x->rc,need);
return x->rc->sum+query(x->lc,need-x->rc->cnt);
}
node*update(node*rt,int l,int r,int pos){
if(l==r)
return new node(l);
if(l+r>>1<pos)
return new node(rt->lc,update(rt->rc,l+r+2>>1,r,pos));
return new node(update(rt->lc,l,l+r>>1,pos),rt->rc);
}
void DEL(node*rt,int l,int r,int pos){
if(l==r) {
delete rt;
return;
}
if(l+r>>1<pos)
DEL(rt->rc,l+r+2>>1,r,pos);
else
DEL(rt->lc,l,l+r>>1,pos);
delete rt;
}
void DELETE(node*rt){
if(!rt)return;
DELETE(rt->lc);
DELETE(rt->rc);
delete rt;
}
node*build(int l,int r){
if(l==r)return new node();
return new node(build(l,l+r>>1),build(l+r+2>>1,r));
}
void dpL(int l,int r,int optl, int optr, int start){
if(l>r) return;
int mid=l+r>>1;
int optmid=optl;
for(int i=optl;i<=optr;i++)
if(2*(start-i)<mid) {
int cost=query(RTL[i],mid-2*(start-i));
if(valL[mid]<cost)
valL[mid]=cost,optmid=i;
}
dpL(l,mid-1,optmid,optr,start);
dpL(mid+1,r,optl,optmid,start);
}
void dpR(int l,int r,int optl, int optr, int start){
if(l>r) return;
int mid=l+r>>1;
int optmid=optl;
for(int i=optl;i<=optr;i++)
if(i-start<mid) {
int cost=query(RTR[i],mid-i+start);
if(valR[mid]<cost)
valR[mid]=cost,optmid=i;
}
dpR(l,mid-1,optl,optmid,start);
dpR(mid+1,r,optmid,optr,start);
}
int proc(II n, II &start, II d,II arr[]){
memset(valL,0,sizeof valL);
memset(valR,0,sizeof valR);
memset(indd,0,sizeof indd);
for(int i=0;i<n;i++)
V[i]=make_pair(arr[i],i);
RTL[start+1]=build(1,n);
RTR[start]=build(1,n);
sort(V,V+n);
for(int i=0;i<n;i++)
indd[V[i].second]=i+1;
for(int i=start+1;i--;)
RTL[i]=update(RTL[i+1],1,n,indd[i]);
for(int i=start;++i<n;)
RTR[i]=update(RTR[i-1],1,n,indd[i]);
dpL(1,d,0,start,start);
dpR(1,d,start,n-1,start);
int ANS=0;
for(int i=0;i<=d;i++)
ANS=max(ANS,valL[i]+valR[d-i]);
reverse(arr,arr+n);
for(int i=0;i<=start;i++)
DEL(RTL[i],1,n,indd[i]);
for(int i=n;--i>start;)
DEL(RTR[i],1,n,indd[i]);
DELETE(RTR[start]);
DELETE(RTL[start+1]);
start=n-1-start;
return ANS;
}
int findMaxAttraction(II n, II start, II d, II attraction[]) {
return max(proc(n,start,d,attraction),proc(n,start,d,attraction));
}
#undef int
#undef II
int main() {
int n, start, d;
int attraction[100000];
int i, n_s;
n_s = scanf("%d %d %d", &n, &start, &d);
for (i = 0 ; i < n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(n, start, d, attraction));
return 0;
}
Compilation message
holiday.cpp: In function 'node* update(node*, long long int, long long int, long long int)':
holiday.cpp:32:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | if(l+r>>1<pos)
| ~^~
holiday.cpp:33:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | return new node(rt->lc,update(rt->rc,l+r+2>>1,r,pos));
| ~~~^~
holiday.cpp:34:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | return new node(update(rt->lc,l,l+r>>1,pos),rt->rc);
| ~^~
holiday.cpp: In function 'void DEL(node*, long long int, long long int, long long int)':
holiday.cpp:41:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | if(l+r>>1<pos)
| ~^~
holiday.cpp:42:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | DEL(rt->rc,l+r+2>>1,r,pos);
| ~~~^~
holiday.cpp:44:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | DEL(rt->lc,l,l+r>>1,pos);
| ~^~
holiday.cpp: In function 'node* build(long long int, long long int)':
holiday.cpp:55:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | return new node(build(l,l+r>>1),build(l+r+2>>1,r));
| ~^~
holiday.cpp:55:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | return new node(build(l,l+r>>1),build(l+r+2>>1,r));
| ~~~^~
holiday.cpp: In function 'void dpL(long long int, long long int, long long int, long long int, long long int)':
holiday.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid=l+r>>1;
| ~^~
holiday.cpp: In function 'void dpR(long long int, long long int, long long int, long long int, long long int)':
holiday.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid=l+r>>1;
| ~^~
holiday.cpp: In function 'int main()':
holiday.cpp:121:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
121 | int i, n_s;
| ^~~
/usr/bin/ld: /tmp/cc4k8wOF.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQVq8ID.o:holiday.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
