Submission #1306932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306932		goppamach	Secret (JOI14_secret)	C++20	100 / 100	342 ms	4440 KiB

secret

#include "secret.h"

const int MAXN = 1000, LG = 10;

int a[MAXN];
int memo[LG][MAXN], mask[MAXN];

void DnC(int l, int r, int depth) {
    if (l >= r) return;
    int m = (l + r) / 2;
    memo[depth][m] = a[m];
    for (int i = m - 1; i >= l; i--) {
        memo[depth][i] = Secret(a[i], memo[depth][i + 1]);
    }
    memo[depth][m + 1] = a[m + 1];
    for (int i = m + 2; i <= r; i++) {
        memo[depth][i] = Secret(memo[depth][i - 1], a[i]);
    }
    for (int i = m + 1; i <= r; i++) mask[i] ^= 1 << depth;
    DnC(l, m, depth + 1);
    DnC(m + 1, r, depth + 1);
}

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

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

• Subtask 1: 100 / 100