Submission #696327

#	Time	Username	Problem	Language	Result	Execution time	Memory
696327		vjudge1	Holiday (IOI14_holiday)	C++14	100 / 100	414 ms	63036 KiB

holiday

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,st,d,a[201000],T[201000]; 
ll su2[6010000];int su[6001000],c,ls[6001000],rs[6001000];
const int I=1e9;
void up(int &o,int lst,int l,int r,int x){
	o=++c;
	su2[o]=su2[lst]+x,su[o]=su[lst]+1,ls[o]=ls[lst],rs[o]=rs[lst];
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)up(ls[o],ls[lst],l,mid,x);
	else up(rs[o],rs[lst],mid+1,r,x);
}
ll kth(int o1,int o2,int l,int r,int k){
	if(l==r)return 1ll*min(su[o1]-su[o2],k)*l;
	int mid=(l+r)>>1,z=su[rs[o1]]-su[rs[o2]];
	if(k<=z)return kth(rs[o1],rs[o2],mid+1,r,k);
	return (su2[rs[o1]]-su2[rs[o2]])+kth(ls[o1],ls[o2],l,mid,k-z);
}
ll calc(int l,int r){
	int k=2*(r-st)+(st-l);
	if(k<d)return kth(T[r],T[l-1],0,I,d-k);
	return 0;
}
ll ans;
void cdq(int l,int r,int pl,int pr){
	if(l>r||pl>pr)return; 
	int ip=-1,mid=(l+r)>>1;
	ll M=-1;
	for(int i=pl;i<=pr;i++){
		ll V=calc(mid,i);
		if(M<V)M=V,ip=i;
	}
	ans=max(ans,M);
	cdq(l,mid-1,pl,ip),cdq(mid+1,r,ip,pr);
}
void sol(){
	c=0;
	for(int i=1;i<=n;i++)up(T[i],T[i-1],0,I,a[i]);
	cdq(1,st,st,n);
}
long long int findMaxAttraction(int N,int sta,int D,int attraction[]){
	n=N,st=sta+1,d=D;
	for(int i=1;i<=n;i++)a[i]=attraction[i-1];
	sol();
	st=n-st+1,reverse(a+1,a+n+1);sol();
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53