Submission #7510

#	Time	Username	Problem	Language	Result	Execution time	Memory
7510		woqja125	Holiday (IOI14_holiday)	C++98	100 / 100	952 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 = 1;
	while(x<b)
	{
		if(k <= IT[2*x].cnt) x = 2*x;
		else
		{
			k -= IT[2*x].cnt;
			x = 2*x+1;
		}
	}
	int f = b, r = x;
	long long ans = 0;
	while(f<r)
	{
		if(f%2 == 1) ans += IT[f++].sum;
		if(r%2 == 0) ans += IT[r--].sum;
		f/=2;r/=2;
	}
	if(f==r) ans += IT[f].sum;
	return ans;
}

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)
				{
//					if(max == 0) loc = l[s];
					continue;
				}
				long long t = MaxKSum(x);
				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