oj.uz

Submission #13702

# Submission time Handle Problem Language Result Execution time Memory
13702 2015-03-07T08:58:55 Z eaststar 케이크 (JOI13_cake) C++
100 / 100
 159 ms 23004 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[300010],t[300010][2],st[300010],p;
long long b[2][300010],ans[300010];
void trav(int n,int s,int e){
    int i=s,j=e,l=t[n][0],r=t[n][1];
    long long sum=a[n];
    if(s==e)ans[n]+=sum,ans[n+1]-=sum;
    if(s>=e)return;
    while(l||r){
        if(a[l]<a[r])sum+=b[j%2][l]-b[j%2][i-1],i=l+1,l=t[l][1];
        else sum+=b[i%2][j]-b[i%2][r-1],j=r-1,r=t[r][0];
    }
    ans[n]+=sum,ans[n+1]-=sum;
    sum=b[s%2][e]-b[s%2][n-1];
    ans[s]+=sum,ans[n]-=sum;
    sum=b[e%2][n]-b[e%2][s-1];
    ans[n+1]+=sum,ans[e+1]-=sum;
    if(t[n][0])trav(t[n][0],s,n-1);
    if(t[n][1])trav(t[n][1],n+1,e);
}
int main(){
    int i,n,mn=2e9,mi,l=1,r,chk=0;
    long long s=0;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d",a+i);
        if(mn>a[i])mn=a[i],mi=i;
    }
    rotate(a+1,a+mi%n+1,a+n+1);
    r=n-1;
    while(l<=r){
        if(a[l]<a[r])s+=chk*a[r--];
        else s+=chk*a[l++];
        chk=!chk;
    }
    ans[n]=s;
    b[1][1]=b[1][2]=a[1];
    for(i=2;i<=n;++i)b[i%2][i+1]=b[i%2][i]=b[i%2][i-2]+a[i];
    for(i=1;i<n;++i){
        while(p&&a[st[p]]>a[i])--p;
        t[i][0]=t[st[p]][1],t[st[p]][1]=i,st[++p]=i;
    }
    a[0]=2e9;
    trav(st[1],1,n-1);
    s=0;
    if(n%2)ans[1]+=a[n];
    for(i=2;i<=n;++i)ans[i]+=ans[i-1];
    if(n%2==0)ans[n]+=a[n];
    rotate(ans+1,ans+n-mi+1,ans+n+1);
    for(i=1;i<=n;++i)printf("%lld\n",ans[i]);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12800 KB Output is correct
2 Correct 0 ms 12800 KB Output is correct
3 Correct 0 ms 12800 KB Output is correct
4 Correct 0 ms 12800 KB Output is correct
5 Correct 0 ms 12868 KB Output is correct
6 Correct 0 ms 12800 KB Output is correct
7 Correct 0 ms 12800 KB Output is correct
8 Correct 0 ms 12800 KB Output is correct
9 Correct 0 ms 12800 KB Output is correct
10 Correct 0 ms 12800 KB Output is correct
11 Correct 0 ms 12800 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 12836 KB Output is correct
2 Correct 27 ms 12800 KB Output is correct
3 Correct 61 ms 12868 KB Output is correct
4 Correct 91 ms 12800 KB Output is correct
5 Correct 82 ms 12800 KB Output is correct
6 Correct 128 ms 12800 KB Output is correct
7 Correct 85 ms 13976 KB Output is correct
8 Correct 156 ms 12800 KB Output is correct
9 Correct 98 ms 12800 KB Output is correct
10 Correct 111 ms 12800 KB Output is correct
11 Correct 159 ms 13460 KB Output is correct
12 Correct 113 ms 14236 KB Output is correct
13 Correct 119 ms 23004 KB Output is correct
14 Correct 152 ms 12800 KB Output is correct
15 Correct 110 ms 14092 KB Output is correct