Submission #1148087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148087		MisterReaper	Marathon Race 2 (JOI24_ho_t3)	C++20	81 / 100	148 ms	24000 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int BOUND = 1000 + 5;
constexpr i64 inf = i64(1E18);

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, L;
    std::cin >> N >> L;
    L++;
    std::vector<int> X(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i];
    }

    int Q;
    std::cin >> Q;
    std::vector<int> S(Q), G(Q), T(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> S[i] >> G[i] >> T[i];
    }

    int n = int(std::set<int>(X.begin(), X.end()).size());

    if (n > BOUND) {
        for (int i = 0; i < Q; ++i) {
            std::cout << "No\n";
        }
        return 0;
    }

    std::vector<int> ans(Q);
    auto work = [&]() -> void {
        auto x = X;
        n = N;

        std::sort(X.begin(), X.end());

        std::vector<int> cnt_map(L);
        for (int i = 0; i < N; ++i) {
            cnt_map[X[i]]++;
        }

        X.erase(std::unique(X.begin(), X.end()), X.end());

        N = int(X.size());

        std::vector<int> pre(N + 1);
        for (int i = 0; i < N; ++i) {
            pre[i + 1] = pre[i] + cnt_map[X[i]];
        }

        std::vector<std::vector<std::array<i64, 2>>> f(N + 1, std::vector<std::array<i64, 2>>(N + 1, {inf, inf}));
        f[0][N][0] = cnt_map[X[0]];
        for (int l = 0; l <= N; ++l) {
            for (int r = N; r > l + 1; --r) {
                i64 cnt = pre[l + 1] + (pre[N] - pre[r]) + 1;
                chmin(f[l + 1][r][0], f[l][r][0] + cnt * (X[l + 1] - X[l]) + cnt_map[X[l + 1]]);
                chmin(f[l][r - 1][1], f[l][r][0] + cnt * (X[r - 1] - X[l]) + cnt_map[X[r - 1]]);
                if (r != N) {
                    chmin(f[l + 1][r][0], f[l][r][1] + cnt * (X[r] - X[l + 1]) + cnt_map[X[l + 1]]);
                    chmin(f[l][r - 1][1], f[l][r][1] + cnt * (X[r] - X[r - 1]) + cnt_map[X[r - 1]]);
                }
            }
        }

        for (int i = 0; i < Q; ++i) {
            int idx = std::upper_bound(X.begin(), X.end(), G[i]) - X.begin();
            if (idx != 0) {
                i64 cost = std::abs(S[i] - X[0]) + f[idx - 1][idx][0] + std::abs(X[idx - 1] - G[i]) * (pre[N] + 1);
                debug(i, cost);
                ans[i] |= cost <= T[i];
                if (idx != N) {
                    cost = std::abs(S[i] - X[0]) + f[idx - 1][idx][1] + std::abs(X[idx] - G[i]) * (pre[N] + 1);
                    ans[i] |= cost <= T[i];
                }
            }
        }

        X = x;
        N = n;
    };
    work();
    for (int i = 0; i < N; ++i) {
        X[i] = L - X[i] - 1;
    }
    for (int i = 0; i < Q; ++i) {
        S[i] = L - S[i] - 1;
        G[i] = L - G[i] - 1;
    }
    work();

    for (int i = 0; i < Q; ++i) {
        std::cout << (ans[i] ? "Yes" : "No") << '\n';
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 19 / 19
• Subtask 7: 0 / 19