Submission #294256

#	Time	Username	Problem	Language	Result	Execution time	Memory
294256		VodkaInTheJar	Holiday (IOI14_holiday)	C++14	100 / 100	2158 ms	18992 KiB

holiday

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

const int maxn = 3e5 + 3; 

int n; 
int idx[maxn], val[maxn]; 
pair <long long, int> tr[maxn * 4]; 

void merge(int v)
{
	tr[v].first = tr[v * 2].first + tr[v * 2 + 1].first;
	tr[v].second = tr[v * 2].second + tr[v * 2 + 1].second;
}

void turn_on(int v, int l, int r, int pos)
{
	if (l == r)
	{
		tr[v] = {val[pos], 1};
		return;
	}
	
	int mid = (l + r) / 2;
	if (pos <= mid)
	turn_on(v * 2, l, mid, pos);
	
	else
	turn_on(v * 2 + 1, mid + 1, r, pos);
	
	merge(v);
}

void turn_off(int v, int l, int r, int pos)
{
	if (l == r)
	{
		tr[v] = {0, 0};
		return;
	}
	
	int mid = (l + r) / 2;
	if (pos <= mid)
	turn_off(v * 2, l, mid, pos);
	
	else
	turn_off(v * 2 + 1, mid + 1, r, pos);
	
	merge(v);
}

long long get(int v, int l, int r, int k)
{
	if (k <= 0)
	return 0;
	
	if (l == r)
	return tr[v].first;
	
	int mid = (l + r) / 2;
	if (tr[v * 2 + 1].second > k)
	return get(v * 2 + 1, mid + 1, r, k);
	
	else 
	return tr[v * 2 + 1].first + get(v * 2, l, mid, k - tr[v * 2 + 1].second);
}

pair <long long, int> f1[maxn], f2[maxn], f3[maxn], f4[maxn];
void calc1(int l, int r, int opt_l, int opt_r, int start)
{
	if (l > r || opt_l > opt_r)
	return;
	
	int mid = (l + r) / 2; 
	long long best = 0;
	int idx_best = -1; 
	for (int i = opt_l; i <= opt_r; i++)
	{
		turn_on(1, 0, n-1, idx[i]);
		
		long long curr_val = get(1, 0, n-1, max(0, mid - (i - start)));  
		if (curr_val > best)
		best = curr_val, idx_best = i; 
	}
	
	f1[mid] = {best, idx_best};
	
	for (int i = opt_l; i <= opt_r; i++)
	turn_off(1, 0, n-1, idx[i]);
	
	calc1(l, mid-1, opt_l, idx_best, start);
	
	for (int i = opt_l; i < idx_best; i++)
	turn_on(1, 0, n-1, idx[i]);
	
	calc1(mid+1, r, idx_best, opt_r, start);
	
	for (int i = opt_l; i < idx_best; i++)
	turn_off(1, 0, n-1, idx[i]);
}

void calc2(int l, int r, int opt_l, int opt_r, int start)
{
	if (l > r || opt_l > opt_r)
	return;
	
	int mid = (l + r) / 2;
    long long best = 0; 
    int idx_best = -1;
    for (int i = opt_r; i >= opt_l; i--)
    {
		turn_on(1, 0, n-1, idx[i]);
		
		long long curr_val = get(1, 0, n-1, max(0, mid - (start - i)));
		if (curr_val > best)
		best = curr_val, idx_best = i; 
	}	
	
	f2[mid] = {best, idx_best};
	
	for (int i = opt_l; i <= opt_r; i++)
	turn_off(1, 0, n-1, idx[i]);
	
	calc2(l, mid-1, idx_best, opt_r, start);
	
	for (int i = opt_r; i > idx_best; i--)
	turn_on(1, 0, n-1, idx[i]);
	
	calc2(mid+1, r, opt_l, idx_best, start);
	
	for (int i = opt_r; i > idx_best; i--)
	turn_off(1, 0, n-1, idx[i]);
}

void calc3(int l, int r, int opt_l, int opt_r, int start)
{
	if (l > r || opt_l > opt_r)
	return;
	
	int mid = (l + r) / 2; 
	long long best = 0;
	int idx_best = -1; 
	for (int i = opt_l; i <= opt_r; i++)
	{
		turn_on(1, 0, n-1, idx[i]);
		
		long long curr_val = get(1, 0, n-1, max(0, mid - (i - start)));  
		if (curr_val > best)
		best = curr_val, idx_best = i; 
	}
	
	f3[mid] = {best, idx_best};
	
	for (int i = opt_l; i <= opt_r; i++)
	turn_off(1, 0, n-1, idx[i]);
	
	calc3(l, mid-1, opt_l, idx_best, start);
	
	for (int i = opt_l; i < idx_best; i++)
	turn_on(1, 0, n-1, idx[i]);
	
	calc3(mid+1, r, idx_best, opt_r, start);
	
	for (int i = opt_l; i < idx_best; i++)
	turn_off(1, 0, n-1, idx[i]);
}

void calc4(int l, int r, int opt_l, int opt_r, int start)
{
	if (l > r || opt_l > opt_r)
	return;
	
	int mid = (l + r) / 2; 
    long long best = 0; 
    int idx_best = -1;
    for (int i = opt_r; i >= opt_l; i--)
    {
		turn_on(1, 0, n-1, idx[i]);
		
		long long curr_val = get(1, 0, n-1, max(0, mid - (start - i)));
		if (curr_val > best)
		best = curr_val, idx_best = i; 
	}	
	
	f4[mid] = {best, idx_best};
	
	for (int i = opt_l; i <= opt_r; i++)
	turn_off(1, 0, n-1, idx[i]);
	
	calc4(l, mid-1, idx_best, opt_r, start);
	
	for (int i = opt_r; i > idx_best; i--)
	turn_on(1, 0, n-1, idx[i]);
	
	calc4(mid+1, r, opt_l, idx_best, start);
	
	for (int i = opt_r; i > idx_best; i--)
	turn_off(1, 0, n-1, idx[i]);
}

long long findMaxAttraction(int _n, int start, int d, int attraction[])
{
	n = _n; 
	vector <pair <int, int> > temp;
	for (int i = 0; i < n; i++)
	temp.push_back({attraction[i], i});
	
	sort (temp.begin(), temp.end());
	for (int i = 0; i < n; i++)
	{
		idx[temp[i].second] = i;
		val[i] = temp[i].first;
	}

	calc1(1, d, start, n-1, start);
	calc2(1, d, 0, start-1, start-1);
	calc3(1, d, start+1, n-1, start+1);
	calc4(1, d, 0, start, start);
	
	long long ans = 0;
	for (int i = 1; i <= d; i++)
	ans = max(ans, f1[i].first + f2[max(0, d-i-(f1[i].second-start)-1)].first);
	
	for (int i = 1; i <= d; i++)
	ans = max(ans, f4[i].first + f3[max(0, d-i-( start-f4[i].second)-1)].first);
	
	if (start == 0)
	return f1[d].first; 
	
	return ans; 
}

/*
int m, start, d, a[maxn];
int main()
{
	cin >> m >> start >> d;
	for (int i = 0; i < m; i++)
	cin >> a[i];
	
	cout << findMaxAttraction(m, start, d, a) << endl; 
}
*/

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