Submission #13297

#	Time	Username	Problem	Language	Result	Execution time	Memory
13297		dohyun0324	케이크 (JOI13_cake)	C++98	100 / 100	166 ms	25068 KiB

cake

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,a[300010],p=1;
int treap[300010][2];
int l,r,p1,p2,s,e,st[300010],top;
ll dap[300010],sume[300010],sumo[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];
    int cnt=0,imsi;
    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][1];
        }
        else{
            if(s%2==0) 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[e+1][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=i+n-p+1; if(t>n) t-=n;
        if(t!=n) dap[t]+=a[t];
        printf("%lld\n",dap[t]);
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90