Submission #473260

#	Time	Username	Problem	Language	Result	Execution time	Memory
473260		ljuba	Secret (JOI14_secret)	C++17	100 / 100	562 ms	4492 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int mxN = 1005;
int mask[mxN];
int value[20][mxN];
int A[mxN];

//maybe too much queries?


void solve(int l, int r, int dep = 0) {
    if(l == r) {
        value[dep][l] = A[l];
        return;
    }

    int m = (l + r) / 2;
    value[dep][m] = A[m];

    for(int i = m-1; i >= l; --i) {
        value[dep][i] = Secret(A[i], value[dep][i+1]);
    }

    value[dep][m+1] = A[m+1];

    for(int i = m+2; i <= r; ++i) {
        value[dep][i] = Secret(value[dep][i-1], A[i]);
    }

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

    solve(l, m, dep+1);
    solve(m+1, r, dep+1);
}

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

    solve(0, N-1);
}

int Query(int L, int R) {
    if(L == R) {
        return A[L];
    }

    int bits = __builtin_ctz(mask[L]^mask[R]);
    int levo = value[bits][L];
    int desno = value[bits][R];
    return Secret(levo, desno);
}

• Subtask 1: 100 / 100