oj.uz

Submission #294256

# Submission time Handle Problem Language Result Execution time Memory
294256 2020-09-08T18:12:00 Z VodkaInTheJar Holiday (IOI14_holiday) C++14
100 / 100
 2158 ms 18992 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 16204 KB Output is correct
2 Correct 1382 ms 11432 KB Output is correct
3 Correct 1916 ms 14644 KB Output is correct
4 Correct 1380 ms 14676 KB Output is correct
5 Correct 2158 ms 12788 KB Output is correct
6 Correct 741 ms 10724 KB Output is correct
7 Correct 1142 ms 8012 KB Output is correct
8 Correct 1303 ms 7964 KB Output is correct
9 Correct 606 ms 13172 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1016 KB Output is correct
2 Correct 33 ms 952 KB Output is correct
3 Correct 33 ms 936 KB Output is correct
4 Correct 33 ms 820 KB Output is correct
5 Correct 28 ms 768 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 7 ms 512 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2043 ms 18772 KB Output is correct
2 Correct 2062 ms 18992 KB Output is correct
3 Correct 603 ms 4460 KB Output is correct
4 Correct 25 ms 640 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 2101 ms 10400 KB Output is correct
9 Correct 2105 ms 10580 KB Output is correct