Submission #872820

#	Time	Username	Problem	Language	Result	Execution time	Memory
872820		rainboy	Feast (NOI19_feast)	C11	100 / 100	58 ms	40532 KiB

feast

#include <stdio.h>

#define N	300000
#define H_	19	/* H_ = ceil(log2(N + 1)) */
#define N_	(1 << H_)
#define INF	0x3f3f3f3f3f3f3f3fLL

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

unsigned int X = 12345;

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

long long ppmn[N_ * 2], ppmx[N_ * 2], ssmn[N_ * 2], ssmx[N_ * 2]; int n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	ppmn[i] = min(ppmn[l], ppmn[r]);
	ppmx[i] = max(ppmx[l], ppmx[r]);
	ssmn[i] = min(ssmn[l], ssmn[r]);
	if (ppmx[l] != -INF && ppmn[r] != INF)
		ssmn[i] = min(ssmn[i], ppmn[r] - ppmx[l]);
	ssmx[i] = max(ssmx[l], ssmx[r]);
	if (ppmn[l] != INF && ppmx[r] != -INF)
		ssmx[i] = max(ssmx[i], ppmx[r] - ppmn[l]);
}

void build(long long *aa, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++) {
		if (i < n)
			ppmn[n_ + i] = aa[i], ppmx[n_ + i] = aa[i];
		else
			ppmn[n_ + i] = INF, ppmx[n_ + i] = -INF;
		ssmn[n_ + i] = ssmx[n_ + i] = 0;
	}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

long long query_mn(int l, int r, int *l_, int *r_) {
	static int qu[(H_ + 1) * 2], qu_[H_ + 1];
	int cnt, cnt_, hl, hr, hl_, hr_, i;
	long long s_;

	cnt = cnt_ = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			qu[cnt++] = l++;
		if ((r & 1) == 0)
			qu_[cnt_++] = r--;
	}
	while (cnt_--)
		qu[cnt++] = qu_[cnt_];
	s_ = INF, hl_ = hr_ = -1;
	for (hr = 0, hl = -1, l = -1; hr < cnt; hr++) {
		r = qu[hr];
		if (s_ > ssmn[r])
			s_ = ssmn[r], hl_ = hr_ = hr;
		if (l != -1 && s_ > ppmn[r] - ppmx[l])
			s_ = ppmn[r] - ppmx[l], hl_ = hl, hr_ = hr;
		if (ppmx[r] != -INF && (hl == -1 || ppmx[l] < ppmx[r]))
			hl = hr, l = r;
	}
	if (hl_ == hr_) {
		i = qu[hl_];
		while (i < n_)
			if (ssmn[i << 1 | 0] == ssmn[i])
				i = i << 1 | 0;
			else if (ssmn[i << 1 | 1] == ssmn[i])
				i = i << 1 | 1;
			else {
				l = i << 1 | 0, r = i << 1 | 1;
				break;
			}
		if (i >= n_)
			l = r = i;
	} else
		l = qu[hl_], r = qu[hr_];
	while (l < n_)
		l = ppmx[l << 1 | 0] == ppmx[l] ? l << 1 | 0 : l << 1 | 1;
	while (r < n_)
		r = ppmn[r << 1 | 0] == ppmn[r] ? r << 1 | 0 : r << 1 | 1;
	*l_ = l - n_, *r_ = r - n_;
	return s_;
}

long long query_mx(int l, int r, int *l_, int *r_) {
	static int qu[(H_ + 1) * 2], qu_[H_ + 1];
	int cnt, cnt_, hl, hr, hl_, hr_, i;
	long long s_;

	cnt = cnt_ = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			qu[cnt++] = l++;
		if ((r & 1) == 0)
			qu_[cnt_++] = r--;
	}
	while (cnt_--)
		qu[cnt++] = qu_[cnt_];
	s_ = -INF, hl_ = hr_ = -1;
	for (hr = 0, hl = -1, l = -1; hr < cnt; hr++) {
		r = qu[hr];
		if (s_ < ssmx[r])
			s_ = ssmx[r], hl_ = hr_ = hr;
		if (l != -1 && s_ < ppmx[r] - ppmn[l])
			s_ = ppmx[r] - ppmn[l], hl_ = hl, hr_ = hr;
		if (ppmn[r] != INF && (hl == -1 || ppmn[l] > ppmn[r]))
			hl = hr, l = r;
	}
	if (hl_ == hr_) {
		i = qu[hl_];
		while (i < n_)
			if (ssmx[i << 1 | 0] == ssmx[i])
				i = i << 1 | 0;
			else if (ssmx[i << 1 | 1] == ssmx[i])
				i = i << 1 | 1;
			else {
				l = i << 1 | 0, r = i << 1 | 1;
				break;
			}
		if (i >= n_)
			l = r = i;
	} else
		l = qu[hl_], r = qu[hr_];
	while (l < n_)
		l = ppmn[l << 1 | 0] == ppmn[l] ? l << 1 | 0 : l << 1 | 1;
	while (r < n_)
		r = ppmx[r << 1 | 0] == ppmx[r] ? r << 1 | 0 : r << 1 | 1;
	*l_ = l - n_, *r_ = r - n_;
	return s_;
}

long long ss[N + 1]; int m;

void solve(int l, int r, int flip) {
	long long s;
	int l_, r_;

	s = !flip ? query_mx(l, r, &l_, &r_) : query_mn(l, r, &l_, &r_);
	if (s != 0) {
		ss[m++] = !flip ? s : -s;
		solve(l, l_, flip), solve(l_, r_, flip ^ 1), solve(r_, r, flip);
	}
}

void sort(long long *ss, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r;
		long long s = ss[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (ss[j] == s)
				j++;
			else if (ss[j] < s) {
				tmp = ss[i], ss[i] = ss[j], ss[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ss[j], ss[j] = ss[k], ss[k] = tmp;
			}
		sort(ss, l, i);
		l = k;
	}
}

int main() {
	static long long aa[N + 1];
	int n, k, h, i;
	long long ans;

	scanf("%d%d", &n, &k);
	for (i = 1; i <= n; i++)
		scanf("%lld", &aa[i]), aa[i] += aa[i - 1];
	build(aa, n + 1);
	solve(0, n, 0);
	sort(ss, 0, m);
	ans = 0;
	for (h = m - 1; h >= 0 && h >= m - k; h--)
		ans += ss[h];
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

feast.c: In function 'main':
feast.c:181:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
feast.c:183:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |   scanf("%lld", &aa[i]), aa[i] += aa[i - 1];
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29