Submission #1273946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273946		MisterReaper	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	285 ms	66192 KiB

Main

// File marathonrace2.cpp created on 28.09.2025 at 19:42:39
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int maxT = int(5E5);
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::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 * (n + 1) / 2 > maxT) {
        for (int i = 0; i < Q; ++i) {
            std::cout << "No\n";
        }
        return 0;
    }

    std::vector<i64> ans(Q, inf);
    auto work = [&]() -> void {
        std::vector<int> cnt(L + 1);
        for (int i = 0; i < N; ++i) {
            cnt[X[i]]++;
        }

        int sizpnts = 0;
        std::vector<int> pnts(n);
        for (int i = 0; i <= L; ++i) {
            if (cnt[i]) {
                pnts[sizpnts++] = i;
            }
        }

        debug(pnts);

        std::vector<int> pre(L + 2);
        for (int i = 0; i <= L; ++i) {
            pre[i + 1] = pre[i] + cnt[i];
        }

        auto count = [&](int l, int r) -> int {
            return pre[r + 1] - pre[l];
        };
        
        std::vector f(n, std::vector(n, std::vector<i64>(2, inf)));
        f[0][n - 1][0] = cnt[pnts[0]];
        for (int len = n; len >= 2; --len) {
            for (int l = 0, r = l + len - 1; r < n; ++l, ++r) {
                chmin(f[l + 1][r][0], f[l][r][0] + cnt[pnts[l + 1]] + 1LL * (pnts[l + 1] - pnts[l]) * (N + 1 - count(pnts[l] + 1, pnts[r])));
                chmin(f[l + 1][r][1], f[l][r][0] + cnt[pnts[r]] + 1LL * (pnts[r] - pnts[l]) * (N + 1 - count(pnts[l] + 1, pnts[r])));
                chmin(f[l][r - 1][0], f[l][r][1] + cnt[pnts[l]] + 1LL * (pnts[r] - pnts[l]) * (N + 1 - count(pnts[l], pnts[r] - 1)));
                chmin(f[l][r - 1][1], f[l][r][1] + cnt[pnts[r - 1]] + 1LL * (pnts[r] - pnts[r - 1]) * (N + 1 - count(pnts[l], pnts[r] - 1)));
            }
        }

        #ifdef DEBUG
            for (int i = 0; i < n; ++i) {
                debug(f[i][i][0], f[i][i][1]);
            }
        #endif

        for (int i = 0; i < Q; ++i) {
            int p = int(std::upper_bound(pnts.begin(), pnts.end(), G[i]) - pnts.begin());
            i64 cost = inf;
            if (p != 0) {
                chmin(cost, std::abs(S[i] - pnts[0]) + f[p - 1][p - 1][0] + 1LL * (G[i] - pnts[p - 1]) * (N + 1));
            }
            if (p != n) {
                chmin(cost, std::abs(S[i] - pnts[0]) + f[p][p][0] + 1LL * (pnts[p] - G[i]) * (N + 1));
            }
            debug(cost);
            chmin(ans[i], cost);
        }
    };

    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();

    debug(ans);

    for (int i = 0; i < Q; ++i) {
        std::cout << (ans[i] <= T[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: 19 / 19