#include<bits/stdc++.h>
using namespace std;
#define dbg(x) "[" << #x " = " << (x) << "]"
#define el "\n"
using ll = long long;
const int N = 3e5 + 5, lg = 19, INF = 2e9;
int n, a[N], spt[lg][N];
ll pref[2][N], ans[N], b[N];
void upd(int p, ll val){
ans[p] += val;
ans[p + 1] -= val;
}
void updR(int l, int r, ll val){
ans[l] += val, ans[r + 1] -= val;
}
int merge_st(int x, int y){
return b[x] < b[y] ? x : y;
}
int MnPos(int l, int r){
int k = 31 - __builtin_clz(r - l + 1);
return merge_st(spt[k][l], spt[k][r - (1 << k) + 1]);
}
ll sum(int l, int r, int t){
return pref[t][r] - pref[t][l - 1];
}
/*
we had min(a[L] -> a[R]) > a[L - 1], a[R + 1]
call MinP: minimum position of [L, R]
now we will divide the segment into [L, MinP - 1], [MinP + 1, R]
so we will calculate the contribute of each segment to the others
with a[MinP] will be the first element we take (we have to take a[MinP] to finish)
the key is to think of what we will take last
*/
ll calc(int l, int r, int m){
int x = l, y = r; ll ans = 0;
while(x < m && m < y){
int nx = MnPos(x, m - 1);
int ny = MnPos(m + 1, y);
if(b[nx] < b[ny]){
// take all [nx + 1, y] before take [x, nx]
int t = (((y - nx) & 1) ^ (nx & 1));
ans = ans + sum(x, nx, t);
x = nx + 1;
}
else{
// take all [x, ny - 1] before take [ny, y]
int t = (((ny - x) & 1) ^ (ny & 1));
ans = ans + sum(ny, y, t);
y = ny - 1;
}
}
ans = ans + (y <= m ? sum(x, m, (m&1)) : (sum(m, y, (m&1))));
return ans;
}
void Dnc(int l, int r){
if(l > r) return;
int nMnP = MnPos(l, r);
upd(nMnP, calc(l, r, nMnP));
Dnc(nMnP + 1, r);
Dnc(l, nMnP - 1);
int bL = (!((nMnP - l) & 1) ? (nMnP & 1) : ((nMnP & 1) ^ 1));
updR(l, nMnP - 1, sum(nMnP, r, bL));
int bR = (!((r - nMnP) & 1) ? (nMnP & 1) : ((nMnP & 1) ^ 1));
updR(nMnP + 1, r, sum(l, nMnP, bR));
}
void Main()
{
cin >> n;
int cMn = 0; a[0] = INF;
for(int i = 1; i <= n; i++){
cin >> a[i];
cMn = (a[i] < a[cMn] ? i : cMn);
}
{
int i = 1, j = cMn;
while(i <= n){
b[i] = a[j], spt[0][i] = i;
(i&1 ? pref[1][i] : pref[0][i]) += b[i];
for(int t = 0; t < 2; t++) pref[t][i] += pref[t][i - 1];
i++;
j = (j + 1 > n ? j + 1 - n : j + 1);
}
for(int i = 1; i < lg; i++){
for(int j = 1; j + (1 << i) - 1 <= n; j++){
spt[i][j] = merge_st(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
}
}
Dnc(2, n);
}
if(n&1) updR(2, n, b[1]);
for(int i = 2; i <= n; i++) ans[i] += ans[i - 1];
{ // Calculate ans[1]
int l = n, r = 2, state = 1;
ans[1] += b[1];
while(l != r){
if(!state) ans[1] += max(b[l], b[r]);
(b[l] > b[r] ? --l : ++r);
state ^= 1;
}
if(!state) ans[1] += b[l];
}
{
for(int i = 1; i <= n; i++) b[i] = ans[i];
int i = cMn, j = 1;
while(j <= n){
ans[i] = b[j];
j++;
i = (i + 1 > n ? 1 : i + 1);
}
}
for(int i = 1; i <= n; i++){
cout << ans[i] << el;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "InvMOD"
if(fopen(name".INP", "r")){
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
}
//system("brute.exe");
int t = 1; while(t--) Main();
return 0;
}
Compilation message (stderr)
cake.cpp: In function 'int main()':
cake.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
157 | freopen(name".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | freopen(name".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |