oj.uz

Submission #283826

# Submission time Handle Problem Language Result Execution time Memory
283826 2020-08-26T07:41:05 Z tinjyu Holiday (IOI14_holiday) C++14
100 / 100
 672 ms 45688 KB 
#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);
	}
	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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 43256 KB Output is correct
2 Correct 303 ms 43564 KB Output is correct
3 Correct 462 ms 43172 KB Output is correct
4 Correct 299 ms 43256 KB Output is correct
5 Correct 641 ms 37752 KB Output is correct
6 Correct 176 ms 15352 KB Output is correct
7 Correct 333 ms 20856 KB Output is correct
8 Correct 405 ms 24696 KB Output is correct
9 Correct 121 ms 14280 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1408 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct
3 Correct 7 ms 1408 KB Output is correct
4 Correct 8 ms 1280 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 44824 KB Output is correct
2 Correct 672 ms 45688 KB Output is correct
3 Correct 102 ms 16504 KB Output is correct
4 Correct 6 ms 1168 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 623 ms 39416 KB Output is correct
9 Correct 655 ms 39304 KB Output is correct