oj.uz

Submission #952438

# Submission time Handle Problem Language Result Execution time Memory
952438 2024-03-23T22:29:27 Z y_combinator Secret (JOI14_secret) C++17
0 / 100
 362 ms 8532 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][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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 4524 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 17982538.
2 Incorrect 97 ms 4540 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 38449312.
3 Incorrect 98 ms 4688 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 696690974.
4 Incorrect 349 ms 8268 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 595821184.
5 Incorrect 353 ms 8248 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 874010704.
6 Incorrect 350 ms 8244 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 805323730.
7 Incorrect 356 ms 8532 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 704129056.
8 Incorrect 355 ms 8232 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 427077896.
9 Incorrect 362 ms 8240 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 281940969.
10 Incorrect 352 ms 8424 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 68832328.