#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using namespace std;
#define F first
#define S second
#define ll long long
#define int ll
#define pb push_back
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define in insert
#define lb lower_bound
#define ub upper_bound
#define y1 yy
#define ppb pop_back
#define ull unsigned ll
const int MAX=5e5+55;
const int inf=1e9;
const int N=2e5;
const int C=331;
const int C1=431;
const int mod=1e9+9;
const int mod1=1e9+9;
#include "holiday.h"
struct node{
int val,cnt;
node(){
val=cnt=0;
}
};
int n;
int a[MAX];
int pos[MAX];
int st;
node t[4*MAX];
void update(int v,int tl,int tr,int pos,int x){
if(tl==tr){
if(x==-1){
t[v].val=0;
t[v].cnt=0;
}
else{
t[v].val=x;
t[v].cnt=1;
}
return;
}
int tm=(tl+tr)/2;
if(pos<=tm)update(2*v,tl,tm,pos,x);
else update(2*v+1,tm+1,tr,pos,x);
t[v].val=t[2*v].val+t[2*v+1].val;
t[v].cnt=t[2*v].cnt+t[2*v+1].cnt;
}
int get(int v,int tl,int tr,int cnt){
if(tl==tr){
if(cnt)return t[v].val;
return 0;
}
int tm=(tl+tr)/2;
if(t[2*v].cnt>=cnt)return get(2*v,tl,tm,cnt);
else return t[2*v].val+get(2*v+1,tm+1,tr,cnt-t[2*v].cnt);
}
int dpR[3][MAX];
int optR[3][MAX];
void calcR(int l,int r,int L,int R,int k){
if(l>r)return;
int m=(l+r)/2;
optR[k][m]=L;
for(int i=L;i<=R;i++){
update(1,1,n,pos[i],a[i]);
int cnt=(m-k*(i-st));
// cout<<i<<" "<<cnt<<"\n";
// cout<<t[1].cnt<<"\n";
int cur=0;
if(cnt>=0){
if(t[1].cnt<=cnt){
cur=t[1].val;
}
else{
cur=get(1,1,n,cnt);
}
}
if(cur>dpR[k][m]){
dpR[k][m]=cur;
optR[k][m]=i;
}
// cout<<L<<" "<<R<<" "<<cnt<<" "<<cur<<"\n";
}
// cout<<k<<" "<<m<<" "<<dpR[k][m]<<" "<<L<<" "<<R<<" "<<get(1,1,n,1)<<"\n";
// return;
if(l==r)return;
for(int i=L;i<=R;i++){
update(1,1,n,pos[i],-1);
}
calcR(l,m-1,L,optR[k][m],k);
for(int i=L;i<=optR[k][m];i++){
update(1,1,n,pos[i],a[i]);
}
calcR(m+1,r,optR[k][m],R,k);
for(int i=L;i<=R;i++){
update(1,1,n,pos[i],-1);
}
}
int dpL[3][MAX];
int optL[3][MAX];
void calcL(int l,int r,int L,int R,int k){
if(l>r)return;
int m=(l+r)/2;
// cout<<m<<" "<<L<<" "<<R<<"\n";
optL[k][m]=R;
// cout<<m<<"\n";
for(int i=R;i>=L;i--){
update(1,1,n,pos[i],a[i]);
int cnt=(m-k*(st-1-i));
// cout<<i<<" "<<cnt<<"\n";
int cur=0;
if(cnt>=0){
if(t[1].cnt<=cnt){
cur=t[1].val;
}
else{
cur=get(1,1,n,cnt);
}
}
if(cur>dpL[k][m]){
dpL[k][m]=cur;
optL[k][m]=i;
}
}
if(l==r)return;
for(int i=L;i<=R;i++){
update(1,1,n,pos[i],-1);
}
// calcL(m+1,r,L,optL[k][m],k);
calcL(l,m-1,optL[k][m],R,k);
for(int i=R;i>=optL[k][m];i--){
update(1,1,n,pos[i],a[i]);
}
calcL(m+1,r,L,optL[k][m],k);
for(int i=L;i<=R;i++){
update(1,1,n,pos[i],-1);
}
}
#undef int
ll findMaxAttraction(int N,int start,int d,int attraction[]) {
#define int ll
n=N;
for(int i=1;i<=n;i++)a[i]=attraction[i-1];
start++;
st=start;
vector<pii> vec;
for(int i=1;i<=n;i++){
// cout<<a[i]<<" "<<i<<"\n";
vec.pb({a[i],i});
}
sort(all(vec));
reverse(all(vec));
for(int i=0;i<sz(vec);i++){
pos[vec[i].S]=i+1;
}
mem(dpR,-1);
mem(dpL,-1);
calcR(1,d,start,n,1);
calcR(1,d,start,n,2);
calcL(1,d,1,start-1,1);
calcL(1,d,1,start-1,2);
int ans=0;
for(int i=1;i<=d;i++){
// cout<<i<<" "<<dpR[2][i]<<" "<<dpL[1][d-i-1]<<"\n";
ans=max(ans,dpR[2][i]+dpL[1][d-i-1]);
ans=max(ans,dpR[1][i]+dpL[2][d-i-2]);
}
return ans;
}
Compilation message
holiday.cpp:10:12: error: 'long long long' is too long for GCC
10 | #define ll long long
| ^~~~
holiday.cpp:11:13: note: in expansion of macro 'll'
11 | #define int ll
| ^~
holiday.h:5:11: note: in expansion of macro 'int'
5 | long long int findMaxAttraction(int n, int start, int d, int attraction[]) ;
| ^~~
holiday.cpp:10:17: error: 'long long long' is too long for GCC
10 | #define ll long long
| ^~~~
holiday.cpp:11:13: note: in expansion of macro 'll'
11 | #define int ll
| ^~
holiday.h:5:11: note: in expansion of macro 'int'
5 | long long int findMaxAttraction(int n, int start, int d, int attraction[]) ;
| ^~~
