Submission #283764

#	Time	Username	Problem	Language	Result	Execution time	Memory
283764		tinjyu	Holiday (IOI14_holiday)	C++14	24 / 100	203 ms	65536 KiB

holiday

#include "holiday.h"
#include <iostream>
using namespace std;
long long int st,d,f1[100005],f2[100005],f3[100005],f4[100005],loc,val,city[100005],count,v[100005],l[2000005],r[2000005],cnt[2000005],sum[2000005],id[1000005],local[1000005];
void qs(int s,int e)
{
	long long int l=s,r=e,mid=(city[s]+city[e])/2;
	while(l<=r)
	{
		while(city[l]>mid)l++;
		while(city[r]<mid)r--;
		if(l<=r)
		{
			swap(city[l],city[r]);
			swap(id[l],id[r]);
			l++;
			r--;
		}
	}
	if(r>s)qs(s,r);
	if(e>l)qs(l,e);
	return ;
}
void clone(int x,int y)
{
	cnt[x]=cnt[y];
	sum[x]=sum[y];
	l[x]=l[y];
	r[x]=r[y];
	return ;
}
long long int change(int node,int s,int e)
{
	count++;
	clone(count,node);
	if(s==e)
	{
		cnt[count]=1;
		sum[count]=val;
		return count;
	}
	long long int now=count;
	if(loc<=(s+e)/2)l[now]=change(l[now],s,(s+e)/2);
	else r[now]=change(r[now],(s+e)/2+1,e);
	cnt[now]=cnt[l[now]]+cnt[r[now]];
	sum[now]=sum[l[now]]+sum[r[now]];
	//cout<<s<<" "<<e<<" "<<cnt[now]<<" "<<sum[now]<<endl;
	return now;
}
long long int find(long long int a,long long int b,long long int k)
{
	if(k>=cnt[b]-cnt[a])return sum[b]-sum[a];
	long long int tmp=find(l[a],l[b],k);
	if(k>cnt[l[b]]-cnt[l[a]])tmp+=find(r[a],r[b],k-cnt[l[b]]+cnt[l[a]]);
	return tmp;
}
void solve1(int s,int e,int l,int r)
{
	if(s>e)return ;
	int mid=(s+e)/2;
	long long int now=0,p=st;
	//cout<<l<<" "<<r<<endl;
	for(int i=l;i<=r;i++)
	{
		if(st-i>mid)continue;
		long long int tmp=find(v[i],v[st],mid-(st-i));
		//cout<<mid<<" "<<i<<" "<<tmp<<" "<<mid-(st-i)<<endl;
		if(tmp>now)
		{
			now=tmp;
			p=i;
		}
	}
	f1[mid]=now;
	solve1(s,mid-1,p,r);
	solve1(mid+1,e,l,p);
	return ;
}
void solve2(int s,int e,int l,int r)
{
	if(s>e)return ;
	int mid=(s+e)/2;
	long long int now=0,p=st;
	for(int i=l;i<=r;i++)
	{
		if(i-st>mid)continue;
		long long int tmp=find(v[st+1],v[i+1],mid-(i-st));
		//cout<<mid<<" "<<i<<" "<<tmp<<" "<<endl;
		if(tmp>now)
		{
			now=tmp;
			p=i;
		}
	}
	f2[mid]=now;
	solve2(s,mid-1,l,p);
	solve2(mid+1,e,p,r);
	return ;
}
void solve3(int s,int e,int l,int r)
{
	if(s>e)return ;
	int mid=(s+e)/2;
	long long int now=0,p=st;
	for(int i=l;i<=r;i++)
	{
		if((st-i)*2>mid)continue;
		long long int tmp=find(v[i],v[st+1],mid-(st-i)*2);
	//	cout<<mid<<" "<<i<<" "<<tmp<<" "<<endl;
		if(tmp>now)
		{
			now=tmp;
			p=i;
		}
	}
	f3[mid]=now;
	solve3(s,mid-1,p,r);
	solve3(mid+1,e,l,p);
	return ;
}
void solve4(int s,int e,int l,int r)
{
	if(s>e)return ;
	int mid=(s+e)/2;
	long long int now=0,p=st;
	for(int i=l;i<=r;i++)
	{
		if((i-st)*2>mid)continue;
		long long int tmp=find(v[st],v[i+1],mid-(i-st)*2);
		if(tmp>now)
		{
			now=tmp;
			p=i;
		}
	}
	f4[mid]=now;
	solve4(s,mid-1,l,p);
	solve4(mid+1,e,p,r);
	return ;
}
long long int findMaxAttraction(int n, int start, int D, int attraction[]) {
	d=D;
	st=start;
	for(int i=0;i<n;i++)id[i]=i,city[i]=attraction[i];
	qs(0,n-1);
	for(int i=0;i<n;i++)
	{
		local[id[i]]=i;
	}
	for(int i=0;i<n;i++)
	{
		v[i+1]=count+1;
		loc=local[i];
		val=attraction[i];
		//cout<<i<<" "<<loc<<" "<<val<<endl;
		change(v[i],0,n-1);
	}
	solve1(0,d,0,st-1);
	solve2(0,d,st+1,n-1);
	solve3(0,d,0,st);
	solve4(0,d,st,n-1);
	long long int ans=0;
	//for(int i=0;i<=d;i++)cout<<f1[i]<<" "<<f2[i]<<" "<<f3[i]<<" "<<f4[i]<<endl;
	for(int i=0;i<=d;i++)
	{
		ans=max(f1[i]+f4[d-i],ans);
		ans=max(f2[i]+f3[d-i],ans);
		//cout<<i<<" "<<ans<<endl;
	}
	return ans;
}

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