oj.uz

Submission #493044

# Submission time Handle Problem Language Result Execution time Memory
493044 2021-12-10T04:00:09 Z izhang05 Secret (JOI14_secret) C++17
100 / 100
 458 ms 4444 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 5, maxs = 10;
int dnc[maxs][maxn], a[maxn], n;

void solve(int l, int r, int d) {
    if (r - l <= 1) {
        return;
    }
    int m = (l + r) / 2;
    dnc[d][m - 1] = a[m - 1];
    dnc[d][m] = a[m];
    for (int i = m - 2; i >= l; --i) {
        dnc[d][i] = Secret(a[i], dnc[d][i + 1]);
    }
    for (int i = m + 1; i < r; ++i) {
        dnc[d][i] = Secret(dnc[d][i - 1], a[i]);
    }
    solve(l, m, d + 1), solve(m, r, d + 1);
}

int query(int l, int r, int lx, int rx, int d) {
    int m = (lx + rx) / 2;

    if (l < m && r > m) {
        return Secret(dnc[d][l], dnc[d][r - 1]);
    } else if (r <= m) {
        return query(l, r, lx, m, d + 1);
    } else {
        return query(l, r, m, rx, d + 1);
    }
}

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

int Query(int l, int r) {
    if (l == r) {
        return a[l];
    }
    return query(l, r + 1, 0, n, 0);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 2372 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 129 ms 2368 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 132 ms 2440 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 458 ms 4344 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 444 ms 4352 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 440 ms 4292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 452 ms 4444 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 444 ms 4392 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 448 ms 4384 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 449 ms 4404 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1