oj.uz

Submission #493039

# Submission time Handle Problem Language Result Execution time Memory
493039 2021-12-10T03:51:35 Z izhang05 Secret (JOI14_secret) C++17
0 / 100
 20000 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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20075 ms 2424 KB Time limit exceeded
2 Execution timed out 20067 ms 2368 KB Time limit exceeded
3 Execution timed out 20087 ms 2476 KB Time limit exceeded
4 Execution timed out 20097 ms 4284 KB Time limit exceeded
5 Execution timed out 20074 ms 4384 KB Time limit exceeded
6 Execution timed out 20087 ms 4344 KB Time limit exceeded
7 Correct 449 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 442 ms 4388 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 445 ms 4428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 445 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1