#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 2e9;
int n, mn = inf, mi;
int a[900010], pw[4444444];
ll cans, sum[2][900010], ans[300010];
const int sz = 1048576;
struct Seg{
int dat[2 * sz];
void ini(){ fill(dat, dat + 2 * sz, inf); }
void upd(int x, int v){
x += sz - 1; dat[x] = v;
for(x /= 2; x; x /= 2) dat[x] = min(dat[2 * x], dat[2 * x + 1]);
}
int mni(int h, int l){
l += sz - 1;
while(l > 1 && !pw[l + 1]){
if(dat[l] < h) break;
l = (l + 1) / 2;
}
while(l < sz){
if(dat[2 * l] < h) l = 2 * l;
else l = 2 * l + 1;
}
return l - sz + 1;
}
int mxi(int h, int r){
r += sz - 1;
while(r > 1 && !pw[r]){
if(dat[r] < h) break;
r = (r - 1) / 2;
}
while(r < sz){
if(dat[2 * r + 1] < h) r = 2 * r + 1;
else r = 2 * r;
}
return r - sz + 1;
}
} S;
void f(int s, int e, int x){
if(e - s - 1 == n - 1){ ans[s > n ? s - n : s] = cans + a[s]; return; }
int l = max(e - n, S.mxi(a[e], s) - 1);
int tb = !(x ^ (s % 2));
ll ts = sum[tb][s] - sum[tb][l];
cans += ts;
f(l, e, x ^ ((s - l) % 2));
cans -= ts;
int r = min(s + n, S.mni(a[s], e) + 1);
tb = !(x ^ (e % 2));
ts = sum[tb][r - 1] - sum[tb][e - 1];
cans += ts;
f(s, r, x ^ ((r - e) % 2));
cans -= ts;
}
void g(int s, int e, int x){
if(e - s - 1 == n) return;
if(x){
if(a[s] > a[e]){
ans[mi] += a[s];
g(s - 1, e, 0);
}
else{
ans[mi] += a[e];
g(s, e + 1, 0);
}
}
else{
if(a[s] > a[e]) g(s - 1, e, 1);
else g(s, e + 1, 1);
}
}
int main(){
scanf("%d", &n);
for(int i = 0; i <= 21; i++) pw[1 << i] = 1;
for(int i = 1; i <= n; i++){
scanf("%d", a + i);
a[n + i] = a[2 * n + i] = a[i];
if(a[i] < mn){
mn = a[i];
mi = i;
}
}
S.ini();
for(int i = 1; i <= 3 * n; i++){
sum[i % 2][i] = sum[i % 2][i - 1] + a[i];
sum[!(i % 2)][i] = sum[!(i % 2)][i - 1];
S.upd(i, a[i]);
}
ans[mi] = mn;
if(n % 2) cans = mn;
f(n + mi - 1, n + mi + 1, !(n % 2));
g(n + mi - 1, n + mi + 1, 0);
for(int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:79:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
cake.cpp:82:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a + i);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1500 ms |
47580 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1500 ms |
47496 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
