Submission #362329

#	Time	Username	Problem	Language	Result	Execution time	Memory
362329		mihai145	Secret (JOI14_secret)	C++14	100 / 100	523 ms	8428 KiB

secret

#include "secret.h"

const int NMAX = 1000;

int _N, _A[NMAX + 5];
int memo[NMAX + 5][NMAX + 5];

void Divide(int st, int dr) {
    if(st == dr) {
        return;
    }

    int mid = (st + dr) >> 1;

    int prevRes = _A[mid - 1];
    for(int l = mid - 1; l >= st; l--) {
        memo[l][mid] = Secret(_A[l - 1], prevRes);
        prevRes = memo[l][mid];
    }

    prevRes = _A[mid];
    for(int r = mid + 2; r <= dr; r++) {
        memo[mid + 1][r] = Secret(prevRes, _A[r - 1]);
        prevRes = memo[mid + 1][r];
    }

    Divide(st, mid);
    Divide(mid + 1, dr);
}

void Init(int N, int A[]) {
//    Secret(0, 1000000000);

    for(int i = 1; i <= N; i++) {
        memo[i][i] = A[i - 1];
    }

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

    Divide(1, N);
}

int Answer(int st, int dr, int L, int R) {
    int mid = (st + dr) >> 1;

    if(L <= mid && mid < R) {
        return Secret(memo[L][mid], memo[mid + 1][R]);
    }

    if(R <= mid)
        return Answer(st, mid, L, R);

    return Answer(mid + 1, dr, L, R);
}

int Query(int L, int R) {
    L++, R++;
    if(L == R) {
        return _A[L - 1];
    }

    return Answer(1, _N, L, R);
}

• Subtask 1: 100 / 100