oj.uz

Submission #1013153

# Submission time Handle Problem Language Result Execution time Memory
1013153 2024-07-03T08:36:12 Z Pannda Secret (JOI14_secret) C++17
100 / 100
 304 ms 8540 KB 
#include "secret.h"

#include <bits/stdc++.h>
using namespace std;

namespace {
    const int n = 1000;
    vector<int> a(n, 0);
    vector<vector<int>> tree(4 * n);
}

void Init(int N, int A[]) {
    copy(A, A + N, a.begin());
    auto build = [&](auto self, int idx, int l, int r) -> void {
        if (l + 1 == r) {
            tree[idx] = {a[l]};
            return;
        }
        int m = (l + r) >> 1;
        self(self, 2 * idx + 1, l, m);
        self(self, 2 * idx + 2, m, r);
        tree[idx].resize(n, -1);
        tree[idx][m - 1] = a[m - 1];
        for (int i = m - 2; i >= l; i--) {
            tree[idx][i] = Secret(a[i], tree[idx][i + 1]);
        }
        tree[idx][m] = a[m];
        for (int i = m + 1; i < r; i++) {
            tree[idx][i] = Secret(tree[idx][i - 1], a[i]);
        }
    };
    build(build, 0, 0, n);
}

int Query(int ql, int qr) {
    qr++;
    int idx = 0, l = 0, r = n;
    while (true) {
        if (l + 1 == r) return a[l];
        int m = (l + r) >> 1;
        if (l <= ql && qr <= m) {
            r = m;
            idx = 2 * idx + 1;
            continue;
        }
        if (m <= ql && qr <= r) {
            l = m;
            idx = 2 * idx + 2;
            continue;
        }
        return Secret(tree[idx][ql], tree[idx][qr - 1]);
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 6740 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
2 Correct 87 ms 6740 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
3 Correct 76 ms 6740 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
4 Correct 278 ms 8532 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
5 Correct 303 ms 8536 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 298 ms 8540 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 304 ms 8496 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 282 ms 8528 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 291 ms 8532 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 283 ms 8532 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1