oj.uz

답안 #372719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372719 2021-03-01T11:08:58 Z BJoozz 케이크 (JOI13_cake) C++14
100 / 100
 247 ms 51308 KB 
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define pb push_back
//#define int long long
const int MAX = 300000+3,M=(1<<25)+1,mod=1e9+7;
void maxx(int &a,int b) {if(b>a) a=b;}
void minn(int &a,int b) {if(b<a) a=b;}
using ii = pair < int ,int > ;
using ll = long long;
int a[MAX];
ll B[MAX][2];
int ST[MAX][20];
ll ans[MAX];
int minu(int i,int j){
    if(a[i]<a[j]) return i;
    else return j;
}
int n;
int LG[MAX];
int id(int u){
    if(u<1) return u+n;
    if(u>n) return u-n;
    return u;
}
int nex[MAX],pre[MAX];
int get(int l,int r){
        int u=r-l+1;
        if(r<l)u+=n;
        u=LG[u];
        return minu(ST[l][u],ST[id(r-(1<<u)+1)][u]);
}
bool tt;
ll getsum(bool x,int l,int r){
    if(r>=l) return B[r][x]-B[l-1][x];
    else return B[n][x]-B[l-1][x]+B[r][x^tt];
}
ll getsum2(bool x,int l,int r){
    if(r>=l) return B[r][x]-B[l-1][x];
    else return B[n][x^tt]-B[l-1][x^tt]+B[r][x];
}



int H;
int dis(int L,int R){
    if(R>=L) return R-L+1;
    else return R-L+1+n;
}
int getdown(int x,int u,int val){
    //if(a[u]<val) return u;
    for(int z=LG[dis(x,u)];z>=0;z--)
        if(a[ ST[id(u-(1<<z))][z] ]>=val ) {
            u=id(u-(1<<z));
        }
    return u;
}
int getup(int x,int u,int val){
    for(int z=LG[dis(u,x)];z>=0;z--)
        if(a[ ST[nex[u]][z] ]>=val ) {
            u=id(u+(1<<z));
        }
    return u;
}

ll cos(int z,int L,int R){

    ll res=a[z];

    if(dis(L,z)<dis(z,R)){
        int i=pre[z],j=nex[z];
        bool ok=1;
        if(L+R<=dis(L,z)*12){
            while(i!=L){
                while(a[j]>a[i]) {
                    ok^=1;if(ok) res+=a[j];j=nex[j];
                    continue;
                }
                ok^=1;if(ok) res+=a[i];i=pre[i];
            }
            while(j!=R){
                ok^=1;if(ok) res+=a[j];j=nex[j];
            }
            return res;
        }
        while(i!=L){
            if(a[j]<a[i]) {if(!ok) res+=a[i];i=pre[i];ok^=1;continue;}
            int m=getup(R,j,a[i]);
            res+=getsum((ok^j)&1,j,m);
            ok^=dis(j,m)&1;
            j=nex[m];
        }
        if(j!=R) res+=getsum((ok^j)&1,j,pre[R]);
        /*while(j!=R){
            if(!ok) res+=a[j];
            ok^=1;
            j=nex[j];
        }*/
    }
    else{
        int i=pre[z],j=nex[z];
        bool ok=1;
        if(L+R<=dis(z,R)*12){
            while(j!=R){
                while(a[i]>a[j]) {
                    ok^=1;if(ok) res+=a[i];i=pre[i];
                    continue;
                }
                ok^=1;if(ok) res+=a[j];j=nex[j];
            }
            while(i!=L){
                ok^=1;if(ok) res+=a[i];i=pre[i];
            }
            return res;
        }

        while(j!=R){
            if(a[i]<a[j]) {if(!ok) res+=a[j];j=nex[j];ok^=1;continue;}
            int m=getdown(L,i,a[j]);
            res+=getsum2((ok^i)&1,m,i);
            ok^=dis(m,i)&1;
            i=pre[m];
        }
        if(i!=L) res+=getsum2((ok^i)&1,nex[L],i);
        /*while(i!=L){
            if(!ok) res+=a[i];
            ok^=1;
            i=pre[i];
        }*/
    }
    return res;
}
void GODOWN(int L,int R,ll sum){
    if(R==id(L+1))return;
    int z=get(id(L+1),id(R-1));
    ans[z]=cos(z,L,R)+sum;

    GODOWN(L,z,sum+getsum( (z^tt^ dis(z,L)) &1,z,pre[R] ));
    GODOWN(z,R,sum+getsum2( (z^tt^dis(R,z))&1,nex[L],z ));
}

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("A.inp", "r", stdin);freopen("A.out", "w", stdout);
    LG[1]=0;
    for(int i=2;i<MAX;i++) LG[i]=LG[i/2]+1;
    cin>>n;
    H=LG[n];
    if(H>=17) H--;
    for(int i=1;i<=n;i++) nex[i]=i+1,pre[i]=i-1;
    pre[1]=n;nex[n]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ST[i][0]=i;
        B[i][0]=B[i-1][0];
        B[i][1]=B[i-1][1];
        B[i][i&1]+=a[i];
    }
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            ST[i][j]=minu(ST[i][j-1],ST[id((i+(1<<j-1))%n)][j-1]);
        }
    }
    int u1=ST[1][19];
    int u2=get(id(u1+1),id(u1-1));
    ll &res = ans[u1];

    tt=n&1;
    res=cos(u1,u2,u2);//return 0;
    if(tt) res+=a[u2];
    if(tt) GODOWN(u1,u1,a[u1]);
    else GODOWN(u1,u1,0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:164:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  164 |             ST[i][j]=minu(ST[i][j-1],ST[id((i+(1<<j-1))%n)][j-1]);
      |                                                   ~^~

Subtask #1
10.0 / 10.0

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

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 14572 KB Output is correct
2 Correct 57 ms 14444 KB Output is correct
3 Correct 60 ms 14596 KB Output is correct
4 Correct 158 ms 32128 KB Output is correct
5 Correct 118 ms 27244 KB Output is correct
6 Correct 175 ms 40044 KB Output is correct
7 Correct 168 ms 41196 KB Output is correct
8 Correct 176 ms 43116 KB Output is correct
9 Correct 191 ms 42992 KB Output is correct
10 Correct 198 ms 43008 KB Output is correct
11 Correct 180 ms 43724 KB Output is correct
12 Correct 217 ms 44524 KB Output is correct
13 Correct 247 ms 51308 KB Output is correct
14 Correct 178 ms 42988 KB Output is correct
15 Correct 208 ms 44184 KB Output is correct