Submission #1246600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246600		colossal_pepe	Overtaking (IOI23_overtaking)	C++20	0 / 100	0 ms	324 KiB

overtaking

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

using ll = long long;

ll l, x;
int n, m;
vector<ll> s;
vector<vector<tuple<ll, ll, int>>> table;
vector<vector<ll>> et;
vector<vector<ll>> dp;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    l = L, x = X;
    m = M;
    s.assign(S.begin(), S.end());
    table.resize(m, vector<tuple<ll, ll, int>>(0));
    for (int i = 0; i < N; i++) {
        if (W[i] <= x) continue;
        table[0].emplace_back(T[i], W[i], table[0].size());
    }
    n = table[0].size();
    et.resize(m, vector<ll>(n));
    for (int i = 0; i < n; i++) {
        et[0][i] = get<0>(table[0][i]);
    }
    for (int i = 1; i < m; i++) {
        sort(table[i - 1].begin(), table[i - 1].end());
        table[i] = table[i - 1];
        for (int j = 0; j < n; j++) {
            auto &[t_nxt, w, idx] = table[i][j];
            t_nxt = et[i - 1][idx] + w * (s[i] - s[i - 1]);
            if (j) t_nxt = max(t_nxt, get<0>(table[i][j - 1]));
            et[i][idx] = get<0>(table[i][j]);
            // cerr << et[i][0] << ' ';
        }
    }
    // cerr << endl;
    dp.resize(m, vector<ll>(n, -1));
    return;
}

int intersection(int start) {
    int l = 0, r = m;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        ll t = start + x * (s[mid] -  s[0]);
        if (t <= get<0>(table[mid].back())) r = mid;
        else l = mid + 1;
    }
    if (start + x * (s[l] - s[0]) <= get<0>(table[l].back())) return l;
    return r;
}

void update(vector<pair<int, int>> &dp_empty, ll arrive) {
    for (auto [i, k] : dp_empty) {
        dp[i][k] = arrive;
    }
}

ll arrival_time(ll Y) {
    vector<pair<int, int>> dp_empty;
    ll start = Y;
    ll arrive = start + x * (s[m - 1] - s[0]);
    if (table[0].empty()) return arrive;
    int i0 = intersection(start);
    // cerr << Y << ' ' << i0 << ' ' << et[i0][0] << ' ' << start + x * (s[i0] - s[0]) << endl;
    if (i0 == m - 1) return get<0>(table[m - 1].back());
    else if (i0 >= m) return arrive;
    if (dp[i0][n - 1] != -1) return dp[i0][n - 1];
    dp_empty.emplace_back(i0, n - 1);
    start = get<0>(table[i0].back());
    for (int i = i0 + 1; i < m; i++) {
        arrive = start + x * (s[i] - s[0]);
        auto itr = lower_bound(table[i - 1].begin(), table[i - 1].end(), make_tuple(start, x, n + 1));
        if (itr == table[i - 1].begin()) {
            // cerr << Y << ' ' << i << ' ' << arrive << endl;
            arrive = start + x * (s[m - 1] - s[i - 1]);
            break;
        } else {
            itr = prev(itr);
            int k = itr - table[i - 1].begin();
            // cerr << Y << ' ' << i << ' ' << k + 1 << ' ' << et[i - 1][0] << endl;
            if (dp[i][k] != -1) {
                arrive = dp[i][k];
                break;
            }
            dp_empty.emplace_back(i, k);
            auto [_, __, j] = *itr;
            arrive = max(arrive, et[i][j]);
        }
        start = arrive;
    }
    update(dp_empty, arrive);
    return arrive;
}

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