Submission #391542

#	Time	Username	Problem	Language	Result	Execution time	Memory
391542		KoD	Secret (JOI14_secret)	C++17	100 / 100	510 ms	4576 KiB

secret

#include "secret.h"

int MSB(int x) {
    return 31 - __builtin_clz(x);
}

int table[10][1000];

void Init(int N, int A[]) {
    for (int i = 0; i < N; ++i) {
        table[0][i] = A[i];
    }
    for (int k = 1; k < 10; ++k) {
        const int len = (1 << k);
        for (int mid = len; mid < N; mid += 2 * len) {
            table[k][mid - 1] = A[mid - 1];
            table[k][mid] = A[mid];
            for (int i = 1; i < len; ++i) {
                table[k][mid - i - 1] = Secret(A[mid - i - 1], table[k][mid - i]);
                if (mid + i < N) {
                    table[k][mid + i] = Secret(table[k][mid + i - 1], A[mid + i]);
                }
            }
        }
    }
}

int Query(int L, int R) {
    if (L == R) {
        return table[0][L];
    }
    const auto k = MSB(L ^ R);
    return Secret(table[k][L], table[k][R]);
}

• Subtask 1: 100 / 100