Submission #527895

#	Time	Username	Problem	Language	Result	Execution time	Memory
527895		rainboy	케이크 (JOI13_cake)	C11	100 / 100	125 ms	20516 KiB

cake

#include <stdio.h>

#define N	300000

void rotate(long long *aa, int n, int i_) {
	static long long bb[N];
	int i;

	for (i = 0; i < n; i++)
		bb[i] = aa[(i + i_) % n];
	for (i = 0; i < n; i++)
		aa[i] = bb[i];
}

long long sum(long long *ss, int l, int r, int p) {
	if (r % 2 != p)
		r--;
	if (l % 2 != p)
		l++;
	return l > r ? 0 : ss[r] - (l < 2 ? 0 : ss[l - 2]);
}

int main() {
	static long long aa[N], ss[N], ans[N];
	static int qu[N], ll[N], rr[N];
	int n, i, i_, l, r, k, cnt;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%lld", &aa[i]);
	i_ = -1;
	for (i = 0; i < n; i++)
		if (i_ == -1 || aa[i_] > aa[i])
			i_ = i;
	rotate(aa, n, (i_ + 1) % n);
	cnt = 0;
	for (i = 0; i < n - 1; i++) {
		while (cnt && aa[qu[cnt - 1]] > aa[i])
			cnt--;
		ll[i] = cnt ? qu[cnt - 1] + 1 : 0;
		qu[cnt++] = i;
	}
	cnt = 0;
	for (i = n - 2; i >= 0; i--) {
		while (cnt && aa[qu[cnt - 1]] > aa[i])
			cnt--;
		rr[i] = cnt ? qu[cnt - 1] - 1 : n - 2;
		qu[cnt++] = i;
	}
	for (i = 0; i < n - 1; i++)
		ss[i] = (i < 2 ? 0 : ss[i - 2]) + aa[i];
	cnt = 0;
	for (i = 0; i < n - 1; i++) {
		long long x;

		x = sum(ss, ll[i], i, rr[i] % 2);
		ans[i + 1] += x, ans[rr[i] + 1] -= x;
		x = sum(ss, i, rr[i], ll[i] % 2);
		ans[ll[i]] += x, ans[i] -= x;
		l = i - 1, r = i + 1, k = 1, x = aa[i];
		while (l >= ll[i] || r <= rr[i])
			if (r > rr[i] || l >= ll[i] && aa[l] > aa[r]) {
				x += sum(ss, ll[l], l, (l + k) % 2);
				k += l - ll[l] + 1, l = ll[l] - 1;
			} else {
				x += sum(ss, r, rr[r], (r + k) % 2);
				k += rr[r] - r + 1, r = rr[r] + 1;
			}
		ans[i] += x, ans[i + 1] -= x;
	}
	if (n % 2 == 1)
		ans[0] += aa[n - 1], ans[n - 1] -= aa[n - 1];
	for (i = 1; i < n; i++)
		ans[i] += ans[i - 1];
	l = r = n - 1, k = 1, ans[n - 1] = aa[n - 1];
	while (r - l + 1 < n)
		if (aa[(l - 1 + n) % n] > aa[(r + 1) % n]) {
			l--;
			if (k++ % 2 == 0)
				ans[n - 1] += aa[(l + n) % n];
		} else {
			r++;
			if (k++ % 2 == 0)
				ans[n - 1] += aa[r % n];
		}
	rotate(ans, n, n - 1 - i_);
	for (i = 0; i < n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}

Compilation message (stderr)

cake.c: In function 'main':
cake.c:62:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |    if (r > rr[i] || l >= ll[i] && aa[l] > aa[r]) {
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~
cake.c:28:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
cake.c:30:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%lld", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90