oj.uz

Submission #59933

# Submission time Handle Problem Language Result Execution time Memory
59933 2018-07-23T10:31:04 Z radoslav11 Holiday (IOI14_holiday) C++14
100 / 100
 531 ms 57056 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 51960 KB Output is correct
2 Correct 49 ms 52072 KB Output is correct
3 Correct 46 ms 52280 KB Output is correct
4 Correct 45 ms 52280 KB Output is correct
5 Correct 43 ms 52280 KB Output is correct
6 Correct 48 ms 52288 KB Output is correct
7 Correct 47 ms 52320 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 53776 KB Output is correct
2 Correct 66 ms 53956 KB Output is correct
3 Correct 72 ms 54016 KB Output is correct
4 Correct 65 ms 54016 KB Output is correct
5 Correct 86 ms 54016 KB Output is correct
6 Correct 52 ms 54016 KB Output is correct
7 Correct 62 ms 54016 KB Output is correct
8 Correct 68 ms 54016 KB Output is correct
9 Correct 57 ms 54016 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 54016 KB Output is correct
2 Correct 55 ms 54016 KB Output is correct
3 Correct 49 ms 54016 KB Output is correct
4 Correct 55 ms 54016 KB Output is correct
5 Correct 50 ms 54016 KB Output is correct
6 Correct 55 ms 54016 KB Output is correct
7 Correct 53 ms 54016 KB Output is correct
8 Correct 52 ms 54016 KB Output is correct
9 Correct 54 ms 54016 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 54044 KB Output is correct
2 Correct 161 ms 55096 KB Output is correct
3 Correct 211 ms 55096 KB Output is correct
4 Correct 50 ms 55096 KB Output is correct
5 Correct 52 ms 55096 KB Output is correct
6 Correct 48 ms 55096 KB Output is correct
7 Correct 57 ms 55096 KB Output is correct
8 Correct 531 ms 56204 KB Output is correct
9 Correct 480 ms 57056 KB Output is correct