oj.uz

Submission #392244

# Submission time Handle Problem Language Result Execution time Memory
392244 2021-04-20T17:29:23 Z rainboy Holiday (IOI14_holiday) C
100 / 100
 619 ms 45464 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 43640 KB Output is correct
2 Correct 449 ms 43688 KB Output is correct
3 Correct 477 ms 43856 KB Output is correct
4 Correct 448 ms 43636 KB Output is correct
5 Correct 619 ms 38396 KB Output is correct
6 Correct 169 ms 15432 KB Output is correct
7 Correct 293 ms 21064 KB Output is correct
8 Correct 349 ms 24968 KB Output is correct
9 Correct 124 ms 14340 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1356 KB Output is correct
2 Correct 6 ms 1356 KB Output is correct
3 Correct 7 ms 1360 KB Output is correct
4 Correct 7 ms 984 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 45024 KB Output is correct
2 Correct 526 ms 45464 KB Output is correct
3 Correct 74 ms 11664 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 416 ms 20488 KB Output is correct
9 Correct 419 ms 20388 KB Output is correct