Submission #283825

#	Time	Username	Problem	Language	Result	Execution time	Memory
283825		tinjyu	Holiday (IOI14_holiday)	C++14	47 / 100	719 ms	43280 KiB

holiday

#include "holiday.h"
#include <iostream>
using namespace std;
long long int temp,st,d,f1[1000005],f2[1000005],f3[1000005],f4[1000005],loc,val,count,sum[3000005];
int v[100005],l[3000005],r[3000005],cnt[3000005],id[100005],local[100005],city[100005];
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 ;
}
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;
}
void find(int a,int b,int k)
{
	if(k>=cnt[b]-cnt[a])
	{
		temp+=sum[b]-sum[a];
		return ;
	}
	find(l[a],l[b],k);
	if(k>cnt[l[b]]-cnt[l[a]])find(r[a],r[b],k-cnt[l[b]]+cnt[l[a]]);
	return ;
}
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;
		temp=0;
		find(v[i],v[st],mid-(st-i));
		long long int tmp=temp;
		//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;
		temp=0;
		find(v[st+1],v[i+1],mid-(i-st));
		long long int tmp=temp;
		//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;
		temp=0;
		find(v[i],v[st+1],mid-(st-i)*2);
		long long int tmp=temp;
	//	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;
		temp=0;
		find(v[st],v[i+1],mid-(i-st)*2);
		long long int tmp=temp;
		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);
	}
	if(n>=10000 && st!=0)return 0;
	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: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53