Submission #145371

#	Time	Username	Problem	Language	Result	Execution time	Memory
145371		faremy	Holiday (IOI14_holiday)	C++14	100 / 100	816 ms	6396 KiB

holiday

#include "holiday.h"

#include <algorithm>


const int MAXN = 1e5;
const int LEAVES = 1 << 17;
const int TSIZE = LEAVES << 1;

long long toVisit[MAXN];
int reindex[MAXN];
int corresLeaf[MAXN];

long long visitSum[TSIZE];
int active[TSIZE];

int left, right;


void upd(int node, long long val, long long type)
{
	if (node != 1)
		upd(node >> 1, val, type);
	visitSum[node] += val * type;
	active[node] += type;
}

long long sum(int node, int want)
{
	if (want <= 0)
		return 0;
	if (want >= active[node])
		return visitSum[node];
	if (node < LEAVES)
		return (sum(node * 2, want) + sum(node * 2 + 1, want - active[node * 2]));
	return 0;
}

long long compute(int lleft, int rleft, int lright, int rright, int startCity, int days)
{
	if (lleft == rleft)
		return 0;
	int pos = (lleft + rleft) / 2;

	while (left > pos)
	{
		left--;
		upd(corresLeaf[left], toVisit[left], 1);
	}

	while (left < pos)
	{
		upd(corresLeaf[left], toVisit[left], -1);
		left++;
	}
	
	while (right < lright)
	{
		upd(corresLeaf[right], toVisit[right], 1);
		right++;
	}

	while (right > lright)
	{
		right--;
		upd(corresLeaf[right], toVisit[right], -1);
	}

	int opt = -1; long long weightOpt = -1;
	int used = 2 * (startCity - pos) + (lright - startCity);

	for (int iEnd = lright; iEnd < rright; iEnd++)
	{
		upd(corresLeaf[iEnd], toVisit[iEnd], 1);
		long long weight = sum(1, std::max(0, days - used));
		used++;

		if (weight > weightOpt)
		{
			opt = iEnd;
			weightOpt = weight;
		}
	}

	for (int iEnd = lright; iEnd < rright; iEnd++)
		upd(corresLeaf[iEnd], toVisit[iEnd], -1);
	long long recurs = std::max(compute(lleft, pos, lright, opt + 1, startCity, days), compute(pos + 1, rleft, opt, rright, startCity, days));
	return std::max(weightOpt, recurs);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
	int cities = n, startCity = start, days = d;
	for (int iCity = 0; iCity < cities; iCity++)
	{
		toVisit[iCity] = attraction[iCity];
		reindex[iCity] = iCity;
	}

	std::sort(reindex, reindex + cities, [](int a, int b) { return toVisit[a] > toVisit[b]; });
	for (int iCity = 0; iCity < cities; iCity++)
		corresLeaf[reindex[iCity]] = LEAVES + iCity;
	
	left = startCity; right = startCity;
	long long maxVisit = compute(0, startCity + 1, startCity, cities, startCity, days);
	
	std::reverse(toVisit, toVisit + cities);
	std::reverse(corresLeaf, corresLeaf + cities);
	std::fill_n(visitSum, TSIZE, 0);
	std::fill_n(active, TSIZE, 0);
	startCity = cities - 1 - startCity;

	left = startCity; right = startCity;
	maxVisit = std::max(maxVisit, compute(0, startCity + 1, startCity, cities, startCity, days));
	return maxVisit;

	return 0;
}

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