Submission #392244

#	Time	Username	Problem	Language	Result	Execution time	Memory
392244		rainboy	Holiday (IOI14_holiday)	C11	100 / 100	619 ms	45464 KiB

holiday

#include "holiday.h"

#define N	100000
#define LG	17	/* LG = ceil(log2(N)) */
#define N_	(N * (LG + 1))

int min(int a, int b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

int aa1[N], n_;
int ll[1 + N_], rr[1 + N_], kk[1 + N_], _; long long xx[1 + N_];

int update(int t, int l, int r, int i) {
	int t_ = _++;

	kk[t_] = kk[t] + 1, xx[t_] = xx[t] + aa1[i];
	if (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			ll[t_] = update(ll[t], l, m, i), rr[t_] = rr[t];
		else
			ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i);
	}
	return t_;
}

long long query(int t, int k) {
	int l, r, m;
	long long sum;

	l = 0, r = n_, sum = 0;
	while (r - l > 1) {
		m = (l + r) / 2;
		if (k < kk[ll[t]])
			r = m, t = ll[t];
		else
			l = m, k -= kk[ll[t]], sum += xx[ll[t]], t = rr[t];
	}
	sum += (long long) min(kk[t], k) * aa1[l];
	return sum;
}

int tt[N];

void solve_(long long *dp, int l, int r, int il, int ir, int c) {
	int m, i, im;
	long long d_;

	if (l == r)
		return;
	m = (l + r) / 2;
	im = -1, d_ = -1;
	for (i = il; i < ir; i++) {
		long long d = m - i * c < 0 ? -1 : query(tt[i], m - i * c);

		if (d_ < d)
			d_ = d, im = i;
	}
	dp[m] = d_;
	solve_(dp, l, m, il, im + 1, c), solve_(dp, m + 1, r, im, ir, c);
}

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *aa_;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
		
		while (j < k)
			if (aa_[ii[j]] == aa_[i_])
				j++;
			else if (aa_[ii[j]] < aa_[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

void solve(int *aa, long long *dp1, long long *dp2, int n, int d_) {
	static int ii[N], inv[N];
	int i, t;

	for (i = 0; i < n; i++)
		ii[i] = i;
	aa_ = aa, sort(ii, 0, n);
	for (i = 0; i < n; i++) {
		inv[ii[i]] = n - 1 - i;
		aa1[n - 1 - i] = aa[ii[i]];
	}
	_ = 1;
	for (i = 0, t = 0; i < n; i++)
		tt[i] = t = update(t, 0, n, inv[i]);
	n_ = n;
	solve_(dp1, 0, d_ + 1, 0, n, 1);
	solve_(dp2, 0, d_ + 1, 0, n, 2);
}

long long findMaxAttraction(int n, int s, int d_, int aa[]) {
	static int aa_[N];
	static long long dp1[N * 2 + N / 2 + 1], dp2[N * 2 + N / 2 + 1], dq1[N * 2 + N / 2 + 1], dq2[N * 2 + N / 2 + 1];
	int i, d;
	long long ans;

	for (i = s; i >= 0; i--)
		aa_[s - i] = aa[i];
	solve(aa_, dp1, dp2, s + 1, d_);
	for (i = s; i < n; i++)
		aa_[i - s] = i == s ? 0 : aa[i];
	solve(aa_, dq1, dq2, n - s, d_);
	ans = 0;
	for (d = 0; d <= d_; d++)
		ans = max(ans, max(dq2[d] + dp1[d_ - d], dp2[d] + dq1[d_ - d]));
	return ans;
}

Compilation message (stderr)

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

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