Submission #129057

#	Time	Username	Problem	Language	Result	Execution time	Memory
129057		Lawliet	Holiday (IOI14_holiday)	C++14	100 / 100	1006 ms	62712 KiB

holiday

#include <bits/stdc++.h>

#define MAX 100010
#define MAXV 1000000010

using namespace std;
typedef long long int lli;

class PersistentSegmentTree
{
	public:

		void copy(int node)
		{
			e.push_back( e[node] );
			d.push_back( d[node] );

			qtd.push_back( qtd[node] );

			sum.push_back( sum[node] );
		}

		int update(int node, int l, int r, int i)
		{
			int newNode = ++curNode;
			copy( node );

			if(l == r)
			{
				qtd[newNode]++;
				sum[newNode] += i;

				return newNode;
			}

			int m = (l + r)/2;

			if(i <= m)
			{
				int aux = update(e[newNode] , l , m , i);
				e[newNode] = aux;
			}
			else
			{
				int aux = update(d[newNode] , m + 1 , r , i);
				d[newNode] = aux;
			}

			qtd[newNode] = qtd[ e[newNode] ] + qtd[ d[newNode] ];
			sum[newNode] = sum[ e[newNode] ] + sum[ d[newNode] ];

			return newNode;
		}

		lli bs(int nodeL, int nodeR, int l, int r, lli k)
		{
			if(l == r) return k*l;

			int m = (l + r)/2;

			int qtdRight = qtd[ d[nodeR] ] - qtd[ d[nodeL] ];
			lli sumRight = sum[ d[nodeR] ] - sum[ d[nodeL] ];

			if(k <= qtdRight) return bs(d[nodeL] , d[nodeR] , m + 1 , r , k);
			return bs(e[nodeL] , e[nodeR] , l , m , k - qtdRight) + sumRight;
		}

		lli getHighests(int l, int r, int k)
		{
			if(k == 0) return 0;

			int qtdInterval = qtd[ root[r] ] - qtd[ root[l - 1] ];
			lli sumInterval = sum[ root[r] ] - sum[ root[l - 1] ];

			if(k >= qtdInterval) return sumInterval;

			return bs(root[l - 1] , root[r] , 0 , MAXV , k);
		}

		void update(int v)
		{
			curVersion++;

			root[curVersion] = update(root[curVersion - 1] , 0 , MAXV , v);
		}

		void init()
		{
			e.clear(); d.clear();
			qtd.clear(); sum.clear();

			e.push_back( 0 ); d.push_back( 0 );
			qtd.push_back( 0 ); sum.push_back( 0LL );

			copy( 0 );

			root[0] = 1;

			curNode = 1;
			curVersion = 0;
		}

	private:

		int curNode;
		int curVersion;

		int root[MAX];

		vector<int> e, d;
		vector<int> qtd;

		vector<lli> sum;
};

int N, S, D;

lli ans;

PersistentSegmentTree SEG;

void DivAndConquer(int l, int r, int optmin, int optmax)
{
	if(l > r) return;

	int mid = (l + r)/2;

	int optInd = optmin;
	lli optAns = -1;

	for(int g = optmin ; g <= optmax ; g++)
	{
		int walkDays = (S - mid) + (g - mid);

		if(walkDays < 0) continue;

		lli curAns = SEG.getHighests(mid , g , D - walkDays);

		if(curAns > optAns)
		{
			optInd = g;
			optAns = curAns;
		}
	}

	ans = max(ans , optAns);

	DivAndConquer(l , mid - 1 , optmin , optInd);
	DivAndConquer(mid + 1 , r , optInd , optmax);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
	N = n; S = start + 1; D = d;

	SEG.init();

	for(int g = 0 ; g < n ; g++)
		SEG.update( attraction[g] );

	DivAndConquer(1 , S , S , N);

	SEG.init();

	for(int g = n - 1 ; g >= 0 ; g--)
		SEG.update( attraction[g] );

	S = N - S + 1;

	DivAndConquer(1 , S , S , N);

	return ans;
}

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