Submission #788031

#	Time	Username	Problem	Language	Result	Execution time	Memory
788031		kamelfanger83	Secret (JOI14_secret)	C++17	100 / 100	384 ms	4520 KiB

secret

#include "secret.h"
#include <vector>

using namespace std;

const int maxD = 10;

vector<int> toright [maxD], toleft [maxD];
int *CA;

void Init(int N, int A[]) {
    CA = A;
    for (int rz = 0; rz < maxD; ++rz) {
        toright[rz].resize(N);
        toleft[rz].resize(N);
    }
    for (int k = 0; k < maxD; k++){
        for (int cen = 1 << k; cen < N; cen += 1 << (k+1)) {
            toright[k][cen - 1] = A[cen - 1];
            for (int lpop = cen - 2; lpop >= cen - (1 << k); --lpop) {
                toright[k][lpop] = Secret(A[lpop], toright[k][lpop + 1]);
            }
            toleft[k][cen] = A[cen];
            for (int rpop = cen + 1; rpop < min(N, cen + (1 << k)); ++rpop) {
                toleft[k][rpop] = Secret(toleft[k][rpop - 1], A[rpop]);
            }
        }
    }
}

int log2C(int n){
    int res = 0;
    while (n >> 1){
        n >>= 1;
        res++;
    }
    return res;
}

int Query(int L, int R) {
    if (L == R) return CA[L];
    int st = log2C(L ^ R);
    return Secret(toright[st][L], toleft[st][R]);
}

• Subtask 1: 100 / 100