Submission #952442

#	Time	Username	Problem	Language	Result	Execution time	Memory
952442		y_combinator	Secret (JOI14_secret)	C++17	100 / 100	369 ms	8596 KiB

secret

#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 / 100