oj.uz

Submission #362329

# Submission time Handle Problem Language Result Execution time Memory
362329 2021-02-02T16:30:10 Z mihai145 Secret (JOI14_secret) C++14
100 / 100
 523 ms 8428 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 4460 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 143 ms 4460 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 144 ms 4588 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 523 ms 8300 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 510 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 506 ms 8368 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 513 ms 8372 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 509 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 503 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 505 ms 8348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1