oj.uz

Submission #13297

# Submission time Handle Problem Language Result Execution time Memory
13297 2015-02-10T15:32:13 Z dohyun0324 케이크 (JOI13_cake) C++
100 / 100
 166 ms 25068 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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