Submission #7512

#	Time	Username	Problem	Language	Result	Execution time	Memory
7512		woqja125	Holiday (IOI14_holiday)	C++98	100 / 100	648 ms	20892 KiB

holiday

#include<algorithm>
#include<functional>
#include"holiday.h"

long long r1[400000];
long long r2[400000];
long long l1[400000];
long long l2[400000];
int l[400000];

struct node
{
	long long sum;
	int cnt;
}IT[300001];

std::pair<int, int> comp[100001];
int S, N, *at;
int b;

void initIT()
{
	for (int i = 0; i < b * 2; i++) IT[i].sum = IT[i].cnt = 0;
}

void update(int x)
{
	long long s = comp[x].first;
	IT[x+=b].sum = s;
	IT[x].cnt = 1;
	while(x/=2)
	{
		IT[x].sum = IT[2*x].sum + IT[2*x+1].sum;
		IT[x].cnt = IT[2*x].cnt + IT[2*x+1].cnt;
	}
}

long long MaxKSum(int k, int x)
{
	if(!k) return 0;
	if(k>=IT[x].cnt) return IT[x].sum;
	if(k>IT[2*x].cnt) return IT[2*x].sum + MaxKSum(k-IT[2*x].cnt, 2*x+1);
	else return MaxKSum(k, 2*x);
}

void setTable(int D, int dir, int dpd, long long *T)
{
	int i, j;
	for(i=1; i<=D; i++)l[i] = -1;
	l[0] = 0; l[D+1] = N;
	while(1)
	{
		initIT();
		int p = 0, s, f;
		while(1)
		{
			for(s=p; s<=D && l[s] != -1; s++);
			if(s==D+1 && p == 0) return;
			if(s==D+1) break;
			s--;
			for(f=s+1; f<=D && l[f] == -1; f++);
			for(j=l[p]; j<l[s]; j++)
			{
				if(j==0 && dir == -1) continue;
				int l = S + dir*j;
				if(l<0 || l >= N) break;
				update(at[l]);
			}
			long long max = 0;
			int loc = l[s];
			int m = (s+f)/2;
			for(j=l[s]; j<=l[f]; j++)
			{
				if(j==0 && dir == -1) continue;
				int y = S + dir*j;
				if(y<0 || y >= N) break;
				update(at[y]);
				int x = m - dpd*j;
				if(x<=0) continue;
				long long t = MaxKSum(x, 1);
				if(max <= t)
				{
					max = t; loc = j;
				}
			}
			T[m] = max;
			l[m] = loc;
			p = f;
		}
	}
}

long long findMaxAttraction(int _N, int _S, int d, int _at[])
{
	S = _S; N = _N; at = _at;
	int i;
	for(i=0; i<N; i++)
	{
		comp[i].first = at[i];
		comp[i].second = i;
	}
	std::sort(comp, comp+i, std::greater<std::pair<int, int> >() );
	for(i=0; i<N; i++)	at[comp[i].second] = i;
	for(b=1; b<N; b*=2);
	
	setTable(d, 1, 1, r1);
	setTable(d, 1, 2, r2);
	setTable(d, -1, 1, l1);
	setTable(d, -1, 2, l2);

	long long t, ans = 0;
	for(i=0; i<=d; i++)
	{
		t = r1[i] + l2[d-i];
		if(ans < t) ans = t;
		t = l1[i] + r2[d-i];
		if(ans < t) ans = t;
	}
    return ans;
}

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