Submission #1126943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126943		fzyzzz_z	Marathon Race 2 (JOI24_ho_t3)	C++20	7 / 100	4 ms	4424 KiB

Main

#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

const int N = 5e5 + 10; 
const int A = 1001; 
const ll inf = (1LL << 61); 

inline void amin(ll & x, ll y) { 
    if (y < x) x = y; 
}

#define int ll

int f[N]; 
ll dp[2][A][A]; 
ll cost[2][A]; 

int32_t main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 

    int N, L; 
    cin >> N >> L; 
    vector<int> X(N); 
    for (auto & x: X) cin >> x; 

    sort(X.begin(), X.end()); 
    vector<pair<int, int>> a(1, {X[0], 0}); 
    for (auto x: X) {
        if (x == a.back().first) a.back().second++; 
        else a.emplace_back(x, 1); 
    }
    int q; 
    cin >> q; 
    int n = a.size(); 
    if (n > 1000) {
        while (q--) {
            cout << "No\n"; 
        }
        exit(0); 
    }

    for (int i = 0; i <= L + 1; ++i) f[i] = 0; 
    for (auto [x, c]: a) f[x + 1] += c; 
    for (int i = 0; i <= L; ++i) f[i + 1] += f[i]; 

    for (int t = 0; t < 2; ++t) {
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) dp[0][i][j] = dp[1][i][j] = inf; 
        dp[t][0][n - 1] = 0; // accounted for all outside of (i, j), at 0L or 1R 

        // cout << "--------------------\n"; 
        // for (auto [x, c]: a) cout << x << ' ' << c << " | "; 
        //     cout << '\n'; 

        for (int len = n - 1; len > 0; --len) {
            for (int l = 0, r = len; r < n; l++, r++) {
                ll has = 0; 
                ll pl = a[l].first; 
                ll pl1 = a[l + 1].first; 
                ll pr1 = a[r - 1].first; 
                ll pr = a[r].first;   
                has += f[pl]; 
                has += f[L + 1] - f[pr + 1]; 
                has++; 

                // amin(dp[1][l][r], dp[0][l][r] + has * (pr - pl)); 
                // amin(dp[0][l][r], dp[1][l][r] + has * (pr - pl)); 
                
                amin(dp[0][l + 1][r], dp[0][l][r] + (has + a[l].second) * (pl1 - pl)); 
                amin(dp[1][l][r - 1], dp[0][l][r] + (has) * (2LL * pr - pl - pr1) + 1LL * a[r].second * (pr - pr1)); 
                
                
                amin(dp[1][l][r - 1], dp[1][l][r] + (has + a[r].second) * (pr - pr1)); 
                amin(dp[0][l + 1][r], dp[1][l][r] + (has) * (pr + pl1 - 2LL * pl) + 1LL * a[l].second * (pl1 - pl));     
                
            }
        }
        for (int i = 0; i < n; ++i) {
            // cost[t][i] = min(dp[0][i][i], dp[1][i][i]);  
            cost[t][i] = dp[t][i][i]; 
        }
    }

    while (q--) {
        int st, en; 
        ll t; 
        cin >> st >> en >> t; 
        t -= f[L + 1]; 

        int lo = 0, hi = n - 1; 
        while (lo < hi) {
            int md = (lo + hi) / 2; 
            if (a[md].first >= en) hi = md; 
            else lo = md + 1; 
        }
        ll ans = inf; 
        for (int i = max(0LL, lo - 3); i <= min(n - 1, lo + 3); ++i) {
            amin(ans, cost[0][i] + abs(st - a[0].first) + (ll) (f[L + 1] + 1) * (abs(en - a[i].first))); 
            amin(ans, cost[1][i] + abs(st - a[n - 1].first) + (ll) (f[L + 1] + 1) * (abs(en - a[i].first))); 
        }
 

        if (ans <= t) {
            cout << "Yes\n"; 
        } else {
            cout << "No\n"; 
        }
    }


}

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