답안 #13297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13297	2015-02-10T15:32:13 Z	dohyun0324	케이크 (JOI13_cake)	C++	100 / 100	166 ms	25068 KB

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	12804 KB	Output is correct
2	Correct	4 ms	12804 KB	Output is correct
3	Correct	0 ms	12804 KB	Output is correct
4	Correct	0 ms	12804 KB	Output is correct
5	Correct	3 ms	12912 KB	Output is correct
6	Correct	0 ms	12804 KB	Output is correct
7	Correct	0 ms	12804 KB	Output is correct
8	Correct	4 ms	12804 KB	Output is correct
9	Correct	0 ms	12804 KB	Output is correct
10	Correct	0 ms	12804 KB	Output is correct
11	Correct	0 ms	12804 KB	Output is correct

Subtask #2

90.0 / 90.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	12872 KB	Output is correct
2	Correct	54 ms	12808 KB	Output is correct
3	Correct	59 ms	12916 KB	Output is correct
4	Correct	87 ms	12804 KB	Output is correct
5	Correct	76 ms	12804 KB	Output is correct
6	Correct	127 ms	12804 KB	Output is correct
7	Correct	166 ms	14244 KB	Output is correct
8	Correct	112 ms	12804 KB	Output is correct
9	Correct	126 ms	12804 KB	Output is correct
10	Correct	103 ms	12804 KB	Output is correct
11	Correct	118 ms	13616 KB	Output is correct
12	Correct	112 ms	14552 KB	Output is correct
13	Correct	124 ms	25068 KB	Output is correct
14	Correct	105 ms	12804 KB	Output is correct
15	Correct	109 ms	14376 KB	Output is correct