Submission #954434

#	Time	Username	Problem	Language	Result	Execution time	Memory
954434		asdasdqwer	Secret (JOI14_secret)	C++14	100 / 100	386 ms	4852 KiB

secret

#include "secret.h"

const int MX = 1000;
int dat[10][MX];
int mask[MX];
int a[MX];


void divi(int l, int r, int lev) {
    if (l == r) return;
    int m = (l+r)/2;
    dat[lev][m] = a[m];
    for (int i=m-1;i>=l;i--) {
        dat[lev][i] = Secret(a[i], dat[lev][i+1]);
    }

    dat[lev][m+1] = a[m+1];
    for (int i=m+2;i<=r;i++) {
        dat[lev][i] = Secret(dat[lev][i-1], a[i]);
    }

    for (int i=m+1;i<=r;i++) {
        mask[i] ^= (1<<lev);
    }

    divi(l, m, lev+1);
    divi(m+1, r, lev+1);
}

void Init(int N, int A[]) {
    for (int i=0;i<N;i++) {
        a[i] = A[i];
    }

    divi(0, N-1, 0);
}

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

• Subtask 1: 100 / 100