#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]);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
