Submission #855179

#	Time	Username	Problem	Language	Result	Execution time	Memory
855179		FairyWinx	Overtaking (IOI23_overtaking)	C++17	100 / 100	2330 ms	179376 KiB

overtaking

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;

vector<vector<long long>> res;
vector<int> s;
vector<pair<int, long long>> t; // speed, time
int n, m;
int x;

vector<vector<int>> who_layer;
vector<vector<long long>> sorted_layer;
vector<vector<int>> nxt_layer;
vector<vector<long long>> res_layer;

const int K = 10;

vector<vector<vector<pair<int, int>>>> up;

void init(int l, int _n, vector<long long> _t, vector<int> _w, 
            int _x, int _m, vector<int> _s) {

    
    x = _x, n = _n, m = _m;
    s = _s;
    t.resize(n);
    for (int i = 0; i < n; ++i) {
        t[i].first = _w[i];
        t[i].second = _t[i];
    }
    sort(rall(t));
    while (t.size() && t.back().first <= x) {
        t.pop_back();
    }
    n = t.size();

    sorted_layer.resize(m);
    who_layer.resize(m, vector<int> (n));
    nxt_layer.resize(m, vector<int> (n));
    res_layer.resize(m, vector<long long> (n));
    up.resize(m, vector (n, vector<pair<int, int>> (K)));

    res.resize(m, vector<long long> (n, -1));
    s = _s;

    for (int i = 0; i < n; ++i) {
        res[0][i] = t[i].second;
    }
    for (int i = 0; i < m - 1; ++i) { // n^2 log
        vector<pair<long long, int>> value;
        for (int j = 0; j < n; ++j) {
            value.emplace_back(res[i][j], j);
        }
        sort(all(value));
        long long mx = 0;
        for (int j = 0; j < n; ++j) {
            long long tmp_max = mx;
            int k = j;
            for (; k < n; ++k) {
                if (value[k].first != value[j].first)
                    break;
                int ind = value[k].second;
                res[i + 1][ind] = max(res[i][ind] + 1ll * t[ind].first * (s[i + 1] - s[i]), mx);    
                tmp_max = max(tmp_max, res[i + 1][ind]);
            }
            mx = tmp_max;
            j = k - 1;
        }
    }

    for (int i = 0; i < m; ++i) {
        vector<int> p(n);
        iota(all(p), 0);
        sort(p.begin(), p.end(), [&] (const int &a, const int &b) {
            return make_pair(res[i][a], -a) < make_pair(res[i][b], -b);
        });
        for (int j = 0; j < n; ++j) {
            sorted_layer[i].push_back(res[i][p[j]]);
            who_layer[i][j] = p[j];
        }
        if (i != m - 1) {
            map<long long, pair<int, int>> low_speed;
            for (int j = 0; j < n; ++j) {
                low_speed[res[i + 1][j]] = max(make_pair(t[j].first, j), low_speed[res[i + 1][j]]);
            }
            for (int j = 0; j < n; ++j) {
                nxt_layer[i][j] = low_speed[res[i + 1][j]].second;
                up[i][j][0] = {nxt_layer[i][j], i + 1};
            }
        } else {
            for (int j = 0; j < n; ++j) {
                up[i][j][0] = {j, i};
            }
        }
    }
    for (int k = 1; k < K; ++k) {
        for (int i = m - 1; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                auto z = up[i][j][k - 1];
                up[i][j][k] = up[z.second][z.first][k - 1];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        res_layer[m - 1][i] = res[m - 1][i];
    }
    for (int i = m - 2; i >= 0; --i) {
        for (int j = 0; j < n; ++j) {
            int ind_low = lower_bound(all(sorted_layer[i]), res[i][j])
                            - sorted_layer[i].begin() - 1;
            if (ind_low == -1) {
                res_layer[i][j] = res[i][j] + 1ll * x * (s.back() - s[i]);
                continue;
            }
            int ind_less = who_layer[i][ind_low];
            pair<int, int> cur_nxt = {ind_less, i};
            for (int k = K - 1; k >= 0; --k) {
                auto jump = up[cur_nxt.second][cur_nxt.first][k];
                if (res[jump.second][jump.first] < res[i][j] + 1ll * x * (s[jump.second] - s[i])) {
                    cur_nxt = jump;
                }
            }
            if (cur_nxt.second == m - 1) {
                res_layer[i][j] = res[i][j] + 1ll * x * (s.back() - s[i]);
            } else {
                cur_nxt = up[cur_nxt.second][cur_nxt.first][0];
                res_layer[i][j] = res_layer[cur_nxt.second][cur_nxt.first];
            }
        }
    }
}

// res_layer[2][0] - неверный.

long long arrival_time(long long y) {
    // int ind = lower_bound(all(sorted_layer[0]), y) - sorted_layer[0].begin() - 1;
    // if (ind == -1) {
    //     return 1ll * x * (s.back()) + y;
    // }
    // ind = who_layer[0][ind];
    // for (int i = 1; i < m; ++i) {
    //     ind = nxt_layer[i - 1][ind];
    //     if (1ll * x * s[i] + y <= res[i][ind]) {
    //         return res_layer[i][ind];
    //     }
    // }
    // return 1ll * x * s.back() + y;

    int ind = lower_bound(all(sorted_layer[0]), y) - sorted_layer[0].begin() - 1;
    if (ind == -1) {
        return 1ll * x * (s.back()) + y;
    }
    ind = who_layer[0][ind];
    pair<int, int> cur_nxt = {ind, 0};
    for (int k = K - 1; k >= 0; --k) {
        auto jump = up[cur_nxt.second][cur_nxt.first][k];
        if (res[jump.second][jump.first] < y + 1ll * x * s[jump.second]) {
            cur_nxt = jump;
        }
    }
    if (cur_nxt.second == m - 1) {
        return y + 1ll * x * (s.back() - s[0]);
    } else {
        cur_nxt = up[cur_nxt.second][cur_nxt.first][0];
        return res_layer[cur_nxt.second][cur_nxt.first];
    }
}

#ifdef LOCAL
int main()
{
    // BEGIN SECRET
    const std::string input_secret = "XwWPuInrOjpekAwGKojzwKw3yVDtdkGS";
    const std::string output_secret = "mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz";
    char secret[1000];
    assert(1 == scanf("%999s", secret));
    if (std::string(secret) != input_secret)
    {
        printf("%s\n", output_secret.c_str());
        printf("PV\n");
        printf("Possible tampering with the input\n");
        fclose(stdout);
        return 0;
    }
    // END SECRET
    int L, N, X, M, Q;
    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
    std::vector<long long> T(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%lld", &T[i]));
    std::vector<int> W(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &W[i]));
    std::vector<int> S(M);
    for (int i = 0; i < M; i++)
        assert(1 == scanf("%d", &S[i]));
    std::vector<long long> Y(Q);
    for (int i = 0; i < Q; i++)
        assert(1 == scanf("%lld", &Y[i]));

    fclose(stdin);

    init(L, N, T, W, X, M, S);
    std::vector<long long> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = arrival_time(Y[i]);

    // BEGIN SECRET
    printf("%s\n", output_secret.c_str());
    printf("OK\n");
    // END SECRET
    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}
#endif

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 35 / 35