Submission #738598

#	Time	Username	Problem	Language	Result	Execution time	Memory
738598		MEGalodon	Secret (JOI14_secret)	C++14	100 / 100	431 ms	4420 KiB

secret

#include "secret.h"
#define MAXN 1001

int dat[MAXN][12];
int mask[MAXN];
void divi(int l, int r, int lev, int A[]){ //zero indexed
    if( l == r ){ dat[l][11] = A[l]; return; }
    int m = (l+r)/2;
    dat[m][lev] = A[m];
    dat[m+1][lev] = A[m+1]; //makes a difference in this case
    for( int i{m-1} ; i >= l ; --i ) dat[i][lev] = Secret(A[i], dat[i+1][lev]);
    for( int i{m+2} ; i <= r ; ++i ) dat[i][lev] = Secret(dat[i-1][lev], A[i]);
    for( int i{m+1} ; i <= r ; ++i ) mask[i] ^= (1<<lev);
    divi(l, m, lev+1, A);
    divi(m+1, r, lev+1, A);
}
void Init(int N, int A[]) {
    divi(0, N-1, 0, A);
    return;
}

int Query(int L, int R) {
    if( L == R ) return dat[L][11];
    int bts = __builtin_ctz(mask[L]^mask[R]);
    int ans = Secret(dat[L][bts], dat[R][bts]);
    return ans;
}

• Subtask 1: 100 / 100