#include<stdio.h>
#include<algorithm>
using namespace std;
int n,a[300010],p=1;
int treap[300010][2];
int l,r,p1,p2,s,e,st[300010],top,odd[300010],even[300010],sumo[300010],sume[300010],dap[300010];
void cake(int x,int y,int pos)
{
if(x>=y) return;
s=x, e=y; p1=treap[pos][0]; p2=treap[pos][1];
while(s!=e){
if(a[p1]<a[p2]){
if(e%2==0) dap[pos]+=sume[p1]-sume[s-1], dap[pos+1]-=sume[p1]-sume[s-1];
else dap[pos]+=sumo[p1]-sumo[s-1], dap[pos+1]-=sumo[p1]-sumo[s-1];
s=p1+1; p1=treap[s][1];
}
else{
if(p2%2==1) dap[pos]+=sume[e]-sume[p2-1], dap[pos+1]-=sume[e]-sume[p2-1];
else dap[pos]+=sumo[e]-sumo[p2-1], dap[pos+1]-=sumo[e]-sumo[p2-1];
e=p2-1; p2=treap[s][0];
}
}
if(y%2==1){
dap[pos+1]+=sumo[pos]-sumo[x-1];
dap[y+1]-=sumo[pos]-sumo[x-1];
}
else{
dap[pos+1]+=sume[pos]-sume[x-1];
dap[y+1]-=sume[pos]-sume[x-1];
}
if(x%2==1){
dap[x]+=sumo[y]-sumo[pos-1];
dap[pos]-=sumo[y]-sumo[pos-1];
}
else{
dap[x]+=sume[y]-sume[pos-1];
dap[pos]-=sume[y]-sume[pos-1];
}
cake(x,pos-1,treap[pos][0]);
cake(pos+1,y,treap[pos][1]);
}
int main()
{
int i,t=1;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[p]>a[i]) p=i;
}
p++; if(p>n) p=1;
rotate(a+1,a+p,a+n+1); n--;
for(i=1;i<=n;i++){
if(a[t]>a[i]) t=i;
while(top && a[st[top]]>a[i]) top--;
treap[i][0]=treap[st[top]][1];
treap[st[top]][1]=i;
st[++top]=i;
}
for(i=1;i<=n;i++){
if(i%2==1) sumo[i]=sumo[i-1]+a[i], sume[i]=sume[i-1];
else sumo[i]=sumo[i-1], sume[i]=sume[i-1]+a[i];
}
a[0]=2147483647;
cake(1,n,t);
for(i=1;i<=n;i++) dap[i]+=dap[i-1];
l=1, r=n; dap[n+1]=a[n+1];
for(i=1;;i++){
if(a[l]>a[r]){
if(i%2==0) dap[n+1]+=a[l];
l++;
}
else{
if(i%2==0) dap[n+1]+=a[r];
r--;
}
if(l>r) break;
}
for(i=1;i<=n;i++){
if(n%2==0) dap[i]+=a[n+1];
}
n++;
for(i=1;i<=n;i++){
t=p+i-2; if(t>n) t-=n;
if(t!=n) dap[t]+=a[t];
printf("%d\n",dap[t]);
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1500 ms |
11628 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
