oj.uz

Submission #952442

# Submission time Handle Problem Language Result Execution time Memory
952442 2024-03-23T22:52:22 Z y_combinator Secret (JOI14_secret) C++17
100 / 100
 369 ms 8596 KB 
#include <utility>
#include <vector>

#include "secret.h"

template <typename F>
class YCombinator {

private:

    const F f = nullptr;

public:

    explicit YCombinator(F&& f) : f(f) {}

    template <typename... Ts>
    decltype(auto) operator()(Ts&&... arguments) const {

        return f(*this, std::forward<Ts>(arguments)...);

    }

};

template <typename F>
YCombinator(F) -> YCombinator<F>;

auto sz = 0;
auto table = std::vector<std::vector<int>>();

auto Init(int n, int* a) -> void {

    sz = n;

    table.resize(sz, std::vector<int>(sz));

    YCombinator(
        [&](auto self, int idx_l, int idx_r) -> void {
            const auto idx_m = (idx_l + idx_r) / 2;
            table[idx_m][idx_m] = a[idx_m];
            table[idx_m + 1][idx_m + 1] = a[idx_m + 1];
            for (auto i = idx_m - 1; i >= idx_l; --i) {
                table[i][idx_m] = Secret(a[i], table[i + 1][idx_m]);
            }
            for (auto i = idx_m + 2; i <= idx_r; ++i) {
                table[idx_m + 1][i] = Secret(table[idx_m + 1][i - 1], a[i]);
            }
            if (idx_l < idx_m) {
                self(idx_l, idx_m);
            }
            if (idx_r > idx_m + 1) {
                self(idx_m + 1, idx_r);
            }
        }
    )(0, sz - 1);

}

auto Query(int l, int r) -> int {

    auto idx_l = 0;
    auto idx_r = sz - 1;

    while (idx_l < idx_r) {
        const auto idx_m = (idx_l + idx_r) / 2;
        if (l <= idx_m && r > idx_m) {
            return Secret(table[l][idx_m], table[idx_m + 1][r]);
        }
        if (r == idx_m) {
            return table[l][r];
        }
        if (l > idx_m) {
            idx_l = idx_m + 1;
        } else {
            idx_r = idx_m;
        }
    }

    return table[idx_l][idx_l];

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4436 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 101 ms 4568 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 101 ms 4432 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 363 ms 8156 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 360 ms 8160 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 361 ms 8476 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 359 ms 8272 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 360 ms 8596 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 360 ms 8160 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 369 ms 8160 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1