oj.uz

답안 #372705

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372705 2021-03-01T10:42:30 Z BJoozz 케이크 (JOI13_cake) C++14
10 / 100
 1500 ms 40172 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 = 320000+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];
        }
        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];
        }
        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:162:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  162 |             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 2284 KB Output is correct
2 Correct 35 ms 2284 KB Output is correct
3 Correct 11 ms 2284 KB Output is correct
4 Correct 4 ms 2284 KB Output is correct
5 Correct 4 ms 2412 KB Output is correct
6 Correct 5 ms 2284 KB Output is correct
7 Correct 5 ms 2304 KB Output is correct
8 Correct 7 ms 2284 KB Output is correct
9 Correct 2 ms 1644 KB Output is correct
10 Correct 1 ms 1644 KB Output is correct
11 Correct 1 ms 1644 KB Output is correct

Subtask #2
0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 348 ms 14700 KB Output is correct
2 Correct 62 ms 14592 KB Output is correct
3 Correct 370 ms 14700 KB Output is correct
4 Correct 147 ms 32108 KB Output is correct
5 Correct 142 ms 27372 KB Output is correct
6 Correct 207 ms 40172 KB Output is correct
7 Execution timed out 1599 ms 33772 KB Time limit exceeded
8 Halted 0 ms 0 KB -