Submission #59933

#	Time	Username	Problem	Language	Result	Execution time	Memory
59933		radoslav11	Holiday (IOI14_holiday)	C++14	100 / 100	531 ms	57056 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
//#include "Lgrader.cpp"

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;	
	int l, r;

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

int psz = 0;
node it[MAXN * 22];

int new_node() { return psz++; } 

int merge(int l, int r)
{
	node &ret = it[new_node()];

	ret.l = l;
	ret.r = r;

	ret.cnt = it[l].cnt + it[r].cnt;
	ret.sum = it[l].sum + it[r].sum;

	return psz - 1;
}

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

int 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));
}

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

	if(l == r) 
	{
		int c = new_node();
		it[c].cnt = it[t].cnt + 1;
		it[c].sum = it[t].sum + cmpr[SZ - x];
		return psz - 1;
	}

	int mid = (l + r) >> 1;
	return merge(add(x, l, mid, it[t].l), add(x, mid + 1, r, it[t].r));
}

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

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

int n, start, d;
int 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]);
}

int64_t answer;

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

	int mid = (l + r) >> 1, opt;
	int64_t v = -(int64_t)1e18;

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

	chkmax(answer, v);

	rec(l, mid - 1, opt_l, opt);
	rec(mid + 1, r, opt, 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++) cmpr.push_back(attraction[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(attraction[i]), 0, SZ, last);  

	rec(0, start, start, n - 1);
	return answer;
}

Compilation message (stderr)

holiday.cpp: In function 'void rec(int, int, int, int)':
holiday.cpp:108:5: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  rec(l, mid - 1, opt_l, opt);
  ~~~^~~~~~~~~~~~~~~~~~~~~~~~
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: 53 / 53