Submission #697783

#	Time	Username	Problem	Language	Result	Execution time	Memory
697783		vjudge1	Holiday (IOI14_holiday)	C++17	100 / 100	597 ms	52232 KiB

holiday

/* ...... */

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

#define inl inline
#define newl putchar('\n')
typedef long long ll;
// typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) begin (p), end (p)
#define empb emplace_back

constexpr int N = 1e5 + 10;
int n, a[N], haji, mxt, arr[N], tt[N], tcnt;
ll f_r[N*3], f_l[N*3], g_r[N*3], g_l[N*3], ans;

struct node { int ls, rs, cnt; ll sum; } t[N*20];
int ntot, rt[N], tar;
inl void post (node &nde) {
	nde.sum = t[nde.ls].sum + t[nde.rs].sum,
	nde.cnt = t[nde.ls].cnt + t[nde.rs].cnt;
}
void _insert (int p, int &q, int l, int r) {
	t[q = ++ntot] = t[p];
	if (l == r) { ++t[q].cnt, t[q].sum += tt[l]; return; }
	int mid = l + r >> 1;
	tar <= mid ? _insert (t[p].ls, t[q].ls, l, mid)
		: _insert (t[p].rs, t[q].rs, mid + 1, r);
	post (t[q]);
}
inl void insert (int p, int &q, int num) {
	tar = num, _insert (p, q, 1, tcnt); }
ll query (int p, int q, int l, int r, int k) {
	if (k <= 0) return 0;
	if (l == r) return (ll) min (t[q].cnt-t[p].cnt, k) * tt[l];
	int mid = l + r >> 1, rht;
	if (t[q].cnt == t[p].cnt) return 0;
	if ((rht = t[t[q].rs].cnt-t[t[p].rs].cnt) >= k)
		return query (t[p].rs, t[q].rs, mid + 1, r, k);
	else return t[t[q].rs].sum - t[t[p].rs].sum + 
		query (t[p].ls, t[q].ls, l, mid, k - rht);
}

int qtot;
template <ll f[], int co, typename F>
void solve (int L, int R, int l, int r, const F &kmx_sum) {
	int mid = L + R >> 1, fr;
	ll res; f[mid] = -1;
	for (int i = l; i <= r; ++i)
		if ((res = kmx_sum (i, mid-co*i)) > f[mid])
			f[mid] = res, fr = i;
	if (mid > L) solve <f, co> (L, mid-1, l, fr, kmx_sum);
	if (mid < R) solve <f, co> (mid+1, R, fr, r, kmx_sum);
}

ll findMaxAttraction (int _n, int _haji, int _mxt, int _a[]) {
	n = _n, haji = ++_haji, mxt = _mxt;
	memcpy (a + 1, _a, n<<2),
	memcpy (tt, a, n + 1<<2);

	sort (tt + 1, tt + n + 1);
	tcnt = unique (tt + 1, tt + n + 1) - tt - 1;
	for (int x = 1; x <= n; ++x)
		insert (rt[x-1], rt[x], a[x] = lower_bound
			(tt + 1, tt + tcnt + 1, a[x]) - tt);
	const auto jun = [&] (int i, int k) {
		return query (rt[haji], rt[i+haji], 1, tcnt, k); };
	const auto gya = [&] (int i, int k) {
		return query (rt[haji-i-1], rt[haji-1], 1, tcnt, k); };
	solve <f_r, 1> (0, mxt, 0, n - haji, jun);
	solve <f_l, 1> (0, mxt, 0, haji - 1, gya);
	solve <g_r, 2> (0, mxt, 0, n - haji, jun);
	solve <g_l, 2> (0, mxt, 0, haji - 1, gya);
	for (auto &f : { f_l, f_r, g_l, g_r })
		for (int x = 1; x <= mxt; ++x)
			f[x] = max (f[x], f[x-1]);
	for (int x = 0; x <= mxt; ++x)
		ans = max (ans, max (f_r[x] + g_l[mxt-x],
			f_l[x] + g_r[mxt-x]));
	for (int x = 0; x < mxt; ++x)
		ans = max (ans, max (f_r[x] + g_l[mxt-x-1],
			f_l[x] + g_r[mxt-x-1]) + tt[a[haji]]);
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void _insert(int, int&, int, int)':
holiday.cpp:32:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int mid = l + r >> 1;
      |            ~~^~~
holiday.cpp: In function 'll query(int, int, int, int, int)':
holiday.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int mid = l + r >> 1, rht;
      |            ~~^~~
holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:65:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   65 |  memcpy (tt, a, n + 1<<2);
      |                 ~~^~~
holiday.cpp: In instantiation of 'void solve(int, int, int, int, const F&) [with ll* f = (& f_r); int co = 1; F = findMaxAttraction(int, int, int, int*)::<lambda(int, int)>]':
holiday.cpp:76:42:   required from here
holiday.cpp:53:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mid = L + R >> 1, fr;
      |            ~~^~~
holiday.cpp: In instantiation of 'void solve(int, int, int, int, const F&) [with ll* f = (& f_l); int co = 1; F = findMaxAttraction(int, int, int, int*)::<lambda(int, int)>]':
holiday.cpp:77:42:   required from here
holiday.cpp:53:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
holiday.cpp: In instantiation of 'void solve(int, int, int, int, const F&) [with ll* f = (& g_r); int co = 2; F = findMaxAttraction(int, int, int, int*)::<lambda(int, int)>]':
holiday.cpp:78:42:   required from here
holiday.cpp:53:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
holiday.cpp: In instantiation of 'void solve(int, int, int, int, const F&) [with ll* f = (& g_l); int co = 2; F = findMaxAttraction(int, int, int, int*)::<lambda(int, int)>]':
holiday.cpp:79:42:   required from here
holiday.cpp:53:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
holiday.cpp: In function 'void solve(int, int, int, int, const F&) [with ll* f = (& g_l); int co = 2; F = findMaxAttraction(int, int, int, int*)::<lambda(int, int)>]':
holiday.cpp:58:29: warning: 'fr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  if (mid > L) solve <f, co> (L, mid-1, l, fr, kmx_sum);
      |               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp: In function 'void solve(int, int, int, int, const F&) [with ll* f = (& g_r); int co = 2; F = findMaxAttraction(int, int, int, int*)::<lambda(int, int)>]':
holiday.cpp:58:29: warning: 'fr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  if (mid > L) solve <f, co> (L, mid-1, l, fr, kmx_sum);
      |               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp: In function 'void solve(int, int, int, int, const F&) [with ll* f = (& f_r); int co = 1; F = findMaxAttraction(int, int, int, int*)::<lambda(int, int)>]':
holiday.cpp:58:29: warning: 'fr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  if (mid > L) solve <f, co> (L, mid-1, l, fr, kmx_sum);
      |               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp: In function 'void solve(int, int, int, int, const F&) [with ll* f = (& f_l); int co = 1; F = findMaxAttraction(int, int, int, int*)::<lambda(int, int)>]':
holiday.cpp:58:29: warning: 'fr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  if (mid > L) solve <f, co> (L, mid-1, l, fr, kmx_sum);
      |               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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