This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
int n,m,D,st,sz,root[100005],a[100005],go[100005];
lint ans;
struct PST{
int cnt;
lint sum;
int l,r;
} T[3500000];
void init(int num,int s,int e)
{
if(s==e)return ;
T[num].l=sz++;
T[num].r=sz++;
init(T[num].l,s,(s+e)/2);
init(T[num].r,(s+e)/2+1,e);
}
void update(int par, int num, int s, int e, int i)
{
T[num].cnt=T[par].cnt + 1;
T[num].sum=T[par].sum + a[i];
if(s==e)return ;
int m=(s+e)/2;
if(m>=go[i])
{
T[num].r=T[par].r;
T[num].l=sz++;
update(T[par].l,T[num].l,s,m,i);
}
else
{
T[num].l=T[par].l;
T[num].r=sz++;
update(T[par].r,T[num].r,m+1,e,i);
}
}
lint getmaxk(int num, int k)
{
if(k==0)return 0;
if(k==T[num].cnt)return T[num].sum;
if(T[T[num].r].cnt >= k)
{
return getmaxk(T[num].r,k);
}
else
{
return T[T[num].r].sum + getmaxk(T[num].l,k - T[T[num].r].cnt);
}
}
lint g(int l,int r,int k)
{
if(k>r-l+1)k=r-l+1;
lint ret1,ret2,ret=0;
int p=max(0,k-(st-l));
int q=min(k,r-st+1);
while(q-p>2)
{
int h=(p+q)/2;
ret1=getmaxk(root[r],h)+(l==st?0:getmaxk(root[l],k-h));
ret2=getmaxk(root[r],h+1)+(l==st?0:getmaxk(root[l],k-h-1));
if(ret1==ret2)p=q=h;
else if(ret1<ret2)p=h;
else q=h+1;
}
for(int i=p;i<=q;i++)
{
ret=max(ret,getmaxk(root[r],i)+(l==st?0:getmaxk(root[l],k-i)));
}
return ret;
}
void f(int p,int q,int optp,int optq,int dir)
{
if(p>q)return ;
int h=(p+q)/2;
int opth;
lint tmp,maxi=-1e9;
for(int j=optp;j<=optq;j++)
{
if(dir)tmp=g(j,h,max(D-(st+h-2*j),0));
else tmp=g(h,j,max(D+(st+h-2*j),0));
if(tmp>maxi)
{
maxi=tmp;
opth=j;
}
}
if(maxi>ans)ans=maxi;
f(p,h-1,optp,opth,dir);
f(h+1,q,opth,optq,dir);
}
lint findMaxAttraction(int N, int start, int d, int attraction[])
{
st=start;n=N;D=d;
for(int i=0;i<n;i++)a[i]=attraction[i];
vector<pii>V;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
V.push_back({a[i],i});
}
sort(V.begin(),V.end());
for(int i=0;i<n;i++)go[V[i].second]=i;
sz=1;
init(0,0,n-1);
for(int i=0;i<n;i++)root[i]=sz++;
for(int i=st;i<n;i++)update(i==st? 0 : root[i-1], root[i], 0, n-1, i);
for(int i=st-1;i>=0;i--)update(i==st-1? 0 : root[i+1], root[i], 0, n-1, i);
f(st,n-1,0,st,1);
f(0,st,st,n-1,0);
return ans;
}
Compilation message (stderr)
holiday.cpp: In function 'lint findMaxAttraction(int, int, int, int*)':
holiday.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
holiday.cpp: In function 'void f(int, int, int, int, int)':
holiday.cpp:96:6: warning: 'opth' may be used uninitialized in this function [-Wmaybe-uninitialized]
96 | f(p,h-1,optp,opth,dir);
| ~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |