Submission #372719

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
372719	2021-03-01T11:08:58 Z	BJoozz	케이크 (JOI13_cake)	C++14	100 / 100	247 ms	51308 KB

cake

#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

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

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