Submission #131483

#	Time	Username	Problem	Language	Result	Execution time	Memory
131483		Mahdi_Jfri	Holiday (IOI14_holiday)	C++14	100 / 100	717 ms	9868 KiB

holiday

#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;

ll dp[maxn];

int a[maxn] , d , root , lu[maxn] , ru[maxn] , l[maxn] , r[maxn];

vector<int> pnt , cmp;

void handle(int lux , int rux , int lx , int rx)
{
	if(lx > rx)
		return;
	int k = (lx + rx) / 2;
	l[k] = lx , r[k] = rx , lu[k] = lux , ru[k] = rux;
	pnt.pb(k);
}

ll sum[maxn * 4];
int t[maxn * 4];

void add(int p , int val , int s = 0 , int e = cmp.size() , int v = 1)
{
	if(e - s < 2)
	{
		t[v] += val;
		sum[v] += cmp[s] * val;
		return;
	}

	int m = (s + e) / 2;
	if(p < m)
		add(p , val , s , m , 2 * v);
	else
		add(p , val , m , e , 2 * v + 1);

	t[v] = t[2 * v] + t[2 * v + 1];
	sum[v] = sum[2 * v] + sum[2 * v + 1];
}

ll get(int k , int s = 0 , int e = cmp.size() , int v = 1)
{
	if(k < 0)
		return 0;
	if(k >= t[v])
		return sum[v];
	if(e - s < 2)
		return 1LL * k * cmp[s];

	int m = (s + e) / 2;
	return get(k , m , e , 2 * v + 1) + get(k - t[2 * v + 1] , s , m , 2 * v);
}

long long int findMaxAttraction(int n, int start, int D, int A[])
{
	root = start;
	d = D;

	for(int i = 0; i < n; i++)
		a[i] = A[i] , cmp.pb(a[i]);

	sort(cmp.begin() , cmp.end());
	cmp.resize(unique(cmp.begin() , cmp.end()) - cmp.begin());
	for(int i = 0; i < n; i++)
		a[i] = lower_bound(cmp.begin() , cmp.end() , a[i]) - cmp.begin();

	int ans = 0;
	handle(0 , root , root , n - 1);
	for(;;)
	{
		if(pnt.empty())
			break;

		memset(t , 0 , sizeof t);
		memset(sum , 0 , sizeof sum);

		auto shit = pnt;
		pnt.clear();

		sort(shit.begin() , shit.end());
		int ln = 0 , rn = -1;

		for(auto p : shit)
		{
			while(rn < p)
			{
				rn++;
				add(a[rn] , 1);
			}

			pair<ll , int> upd = {-1 , 0};
			for(int i = lu[p]; i <= ru[p]; i++)
			{
				while(ln < i)
				{
					add(a[ln] , -1);
					ln++;
				}

				int x = d - abs(i - root) - abs(p - root) - min(abs(i - root) , abs(p - root));
				ll sum = get(x);
				upd = max(upd , make_pair(sum , i));
			}

			dp[p] = upd.first;
			handle(lu[p] , upd.second , l[p] , p - 1);
			handle(upd.second , ru[p] , p + 1 , r[p]);
		}
	}

	return *max_element(dp + root , dp + n);
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:73:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans = 0;
      ^~~

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