uoj#29. 【IOI2014】Holiday

时间:2024-08-27 15:35:56

http://uoj.ac/problem/29

经过的点集一定是一个包含start的区间,为了经过这个区间内所有点,必须先到达一个区间端点,再到达另一个区间端点,剩余的步数则贪心选区间内最大价值的点。显然决策单调,于是可以分治,用可持久化线段树快速求出区间前k大数之和。

#include"holiday.h"
#include<cstring>
#include<algorithm>
typedef long long i64;
const int N=;
i64 ans=;
int v[N],*vs[N],S,D;
struct node{
node*c[];
int sz;
i64 s;
}ns[N*],*np=ns,*rt[N];
i64 kmx(int L,int R,int x){
node*w1=rt[L],*w2=rt[R+];
i64 sum=;
for(int i=;i>=;--i){
int s=w1->c[]->sz-w2->c[]->sz;
if(s<=x){
x-=s;
sum+=w1->c[]->s-w2->c[]->s;
w1=w1->c[];
w2=w2->c[];
}else{
w1=w1->c[];
w2=w2->c[];
}
}
return sum;
}
node*ins(node*w,int x,int v){
node*u=++np,*u0=u;
for(int i=;i>=;--i){
int d=x>>i&;
u->c[d^]=w->c[d^];
u=u->c[d]=++np;w=w->c[d];
u->sz=w->sz+;
u->s=w->s+v;
}
return u0;
}
void calc1(int L,int R,int l,int r){
if(L>R)return;
int M=L+R>>,m=l,res=D-(S-M)*-(l-S);
i64 mv=-;
for(int i=l;i<=r&&res>=;++i,--res){
i64 v=kmx(M,i,res);
if(v>mv)mv=v,m=i;
}
if(ans<mv)ans=mv;
calc1(L,M-,l,m);
calc1(M+,R,m,r);
}
void calc2(int L,int R,int l,int r){
if(L>R)return;
int M=L+R>>,m=r,res=D-(M-S)*-(S-r);
i64 mv=-;
for(int i=r;i>=l&&res>=;--i,--res){
i64 v=kmx(i,M,res);
if(v>mv)mv=v,m=i;
}
if(ans<mv)ans=mv;
calc2(L,M-,l,m);
calc2(M+,R,m,r);
}
bool cmp(int*a,int*b){
return *a>*b;
}
i64 findMaxAttraction(int n,int start,int d,int attr[]){
rt[n]=ns->c[]=ns->c[]=ns;
memcpy(v,attr,sizeof(int)*n);
for(int i=;i<n;++i)vs[i]=v+i;
std::sort(vs,vs+n,cmp);
for(int i=;i<n;++i)*vs[i]=i;
for(int i=n-;i>=;--i)rt[i]=ins(rt[i+],v[i],attr[i]);
D=d;S=start;
calc1(std::max(,S-d/),S,S,n-);
calc2(S,std::min(n-,S+d/),,S);
return ans;
}
#include"grader.cpp"