Submission #527895

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
527895	2022-02-18T16:31:46 Z	rainboy	케이크 (JOI13_cake)	C	100 / 100	125 ms	20516 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	588 KB	Output is correct
2	Correct	2 ms	552 KB	Output is correct
3	Correct	3 ms	588 KB	Output is correct
4	Correct	2 ms	588 KB	Output is correct
5	Correct	3 ms	588 KB	Output is correct
6	Correct	2 ms	548 KB	Output is correct
7	Correct	2 ms	588 KB	Output is correct
8	Correct	2 ms	608 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	1 ms	288 KB	Output is correct

Subtask #2

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	6660 KB	Output is correct
2	Correct	29 ms	6704 KB	Output is correct
3	Correct	39 ms	6600 KB	Output is correct
4	Correct	70 ms	14664 KB	Output is correct
5	Correct	64 ms	13056 KB	Output is correct
6	Correct	95 ms	19368 KB	Output is correct
7	Correct	82 ms	19680 KB	Output is correct
8	Correct	93 ms	19396 KB	Output is correct
9	Correct	92 ms	19400 KB	Output is correct
10	Correct	89 ms	19940 KB	Output is correct
11	Correct	104 ms	19484 KB	Output is correct
12	Correct	81 ms	19904 KB	Output is correct
13	Correct	96 ms	20016 KB	Output is correct
14	Correct	80 ms	20516 KB	Output is correct
15	Correct	125 ms	19484 KB	Output is correct