Submission #7509

#	Time	Username	Problem	Language	Result	Execution time	Memory
7509		woqja125	Holiday (IOI14_holiday)	C++98	24 / 100	5000 ms	19328 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];

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=0; i<=D; i++)
	{
		long long max = 0;
		initIT();
		for(j=0; j<N; j++)
		{
			if(j==0 && dir == 1) continue;
			int l = S+j*dir;
			if(l<0 || l>=N) break;
			update(at[l]);
			int t = i - j*dpd;
			if(t<=0) continue;
			long long sum = MaxKSum(t);
			if(max < sum) max = sum;
		}
		T[i] = max;
	}
}

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: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53