Submission #59922

#	Time	Username	Problem	Language	Result	Execution time	Memory
59922		radoslav11	Holiday (IOI14_holiday)	C++14	47 / 100	559 ms	66560 KiB

holiday

#include <bits/stdc++.h>
//#include "Lgrader.cpp"
#define endl '\n'

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (int)1e5 + 42;

struct node
{
	int cnt;
	int64_t sum;	
	node *l, *r;

	node() { l = r = nullptr; sum = cnt = 0; }
};

using pnode = node*;

pnode merge(pnode l, pnode r)
{
	pnode ret = new node();

	ret->l = l;
	ret->r = r;

	ret->cnt = l->cnt + r->cnt;
	ret->sum = l->sum + r->sum;

	return ret;
}

vector<int> cmpr;
int get(int x) { return lower_bound(cmpr.begin(), cmpr.end(), x) - cmpr.begin(); }
int SZ;

pnode build(int l, int r)
{
	if(l == r)
		return new node();

	int mid = (l + r) >> 1;
	return merge(build(l, mid), build(mid + 1, r));
}

pnode add(int x, int l, int r, pnode t)
{
	if(x < l || x > r)
		return t;

	if(l == r) 
	{
		pnode it = new node();
		it->cnt = t->cnt + 1;
		it->sum = t->sum + cmpr[SZ - x];
		return it;
	}

	int mid = (l + r) >> 1;
	return merge(add(x, l, mid, t->l), add(x, mid + 1, r, t->r));
}

int64_t get(int k, int l, int r, pnode A, pnode B)
{
	if(l == r)
	{
		int c = min(k, A->cnt - B->cnt);
		int64_t ret = c * 1ll * cmpr[SZ - l];
		return ret;
	}

	int mid = (l + r) >> 1;
	if(A->l->cnt - B->l->cnt < k) return A->l->sum - B->l->sum + get(k - (A->l->cnt - B->l->cnt), mid + 1, r, A->r, B->r);
	else return get(k, l, mid, A->l, B->l);
}

int n, a[MAXN], start, d;
pnode t[MAXN], emp, last;

int64_t eval(int l, int r)
{
	int cnt = (r - l) * 2 - max(abs(start - l), abs(start - r)); 
	cnt = max(0, d - cnt);	
	if(l == 0) return get(cnt, 0, SZ, t[r], emp);
	else return get(cnt, 0, SZ, t[r], t[l - 1]);
}

int opt[MAXN];
int64_t value[MAXN];

void rec(int l, int r, int opt_l, int opt_r)
{
	if(l > r)
		return;

	int mid = (l + r) >> 1;

	opt[mid] = l;
	value[mid] = -(int64_t)1e18;

	for(int i = opt_l; i <= opt_r; i++)
		if(chkmax(value[mid], eval(mid, i)))
			opt[mid] = i;

	rec(l, mid - 1, opt_l, opt[mid]);
	rec(mid + 1, r, opt[mid], opt_r);
}

long long findMaxAttraction(int n, int start, int d, int attraction[])
{
	::n = n;
	::start = start;
	::d = d;
	for(int i = 0; i < n; i++)

		a[i] = attraction[i];

	for(int i = 0; i < n; i++) cmpr.push_back(a[i]);
	sort(cmpr.begin(), cmpr.end());
	cmpr.erase(unique(cmpr.begin(), cmpr.end()), cmpr.end());
	SZ = cmpr.size() - 1;

	last = emp = build(0, SZ);
	for(int i = 0; i < n; i++)
		last = t[i] = add(SZ - get(a[i]), 0, SZ, last);  

	rec(0, start, start, n - 1);

	int64_t answer = 0;
	for(int i = 0; i < n; i++)
		chkmax(answer, value[i]);

	/*for(int i = 0; i <= start; i++)
		for(int j = start; j < n; j++)
			//cout << i << " " << j << " : " << eval(i, j) << endl; 
			chkmax(answer, eval(i, j));
	*/

	return answer;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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