Submission #1094205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094205		Lechaa09	Overtaking (IOI23_overtaking)	C++17	Compilation error	0 ms	0 KiB

overtaking

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 2;

int L, N, X, M, Q;
vector<ll> T, W, S;
vector<vector<ll>> t_arrival; // t_arrival[i][j]: arrival time of bus i at station j
vector<vector<ll>> e_expected; // e_expected[i][j]: expected arrival time of bus i at station j

// For each station j, store t_k_j_minus_1 and prefix_max_e_k_j for scheduled buses
vector<vector<ll>> t_k_j_minus_1; // t_k_j_minus_1[j][i]: arrival time at station j-1 for bus i
vector<vector<ll>> e_k_j;         // e_k_j[j][i]: expected arrival time at station j for bus i
vector<vector<ll>> prefix_max_e_k_j; // prefix_max_e_k_j[j][i]: max e_k_j up to index i

void init(int L_input, int N_input, int64_t T_input[], int W_input[], int X_input, int M_input, int S_input[]) {
    L = L_input;
    N = N_input;
    X = X_input;
    M = M_input;
    T.assign(T_input, T_input + N);
    W.assign(W_input, W_input + N);
    S.assign(S_input, S_input + M);

    // Precompute t_arrival and e_expected for scheduled buses
    t_arrival.assign(N, vector<ll>(M));
    e_expected.assign(N, vector<ll>(M));

    for (int i = 0; i < N; ++i) {
        t_arrival[i][0] = T[i]; // t_i,0 = T[i]
    }

    for (int j = 1; j < M; ++j) {
        // Prepare to sort buses by t_i,j-1
        vector<pair<ll, int>> buses; // (t_i,j-1, i)
        for (int i = 0; i < N; ++i) {
            buses.push_back({t_arrival[i][j - 1], i});
        }
        sort(buses.begin(), buses.end());

        ll current_max_e = -INF;
        for (auto &p : buses) {
            int i = p.second;
            ll d_j = S[j] - S[j - 1];
            e_expected[i][j] = t_arrival[i][j - 1] + W[i] * d_j; // e_i,j
            t_arrival[i][j] = max(e_expected[i][j], current_max_e);
            current_max_e = max(current_max_e, e_expected[i][j]);
        }
    }

    // Precompute t_k_j_minus_1, e_k_j, and prefix_max_e_k_j for each station
    t_k_j_minus_1.assign(M, vector<ll>(N));
    e_k_j.assign(M, vector<ll>(N));
    prefix_max_e_k_j.assign(M, vector<ll>(N));

    for (int j = 1; j < M; ++j) {
        vector<pair<ll, int>> buses; // (t_i,j-1, i)
        for (int i = 0; i < N; ++i) {
            buses.push_back({t_arrival[i][j - 1], i});
        }
        sort(buses.begin(), buses.end());
        for (int idx = 0; idx < N; ++idx) {
            int i = buses[idx].second;
            t_k_j_minus_1[j][idx] = t_arrival[i][j - 1];
            e_k_j[j][idx] = e_expected[i][j];
        }
        // Compute prefix_max_e_k_j
        prefix_max_e_k_j[j].resize(N);
        prefix_max_e_k_j[j][0] = e_k_j[j][0];
        for (int idx = 1; idx < N; ++idx) {
            prefix_max_e_k_j[j][idx] = max(prefix_max_e_k_j[j][idx - 1], e_k_j[j][idx]);
        }
    }
}

int64_t arrival_time(int64_t Y) {
    ll t_N_j_minus_1 = Y; // t_N,0 = Y
    for (int j = 1; j < M; ++j) {
        ll d_j = S[j] - S[j - 1];
        ll e_N_j = t_N_j_minus_1 + X * d_j;
        // Buses k where t_k,j-1 < t_N,j-1
        vector<ll> &t_k = t_k_j_minus_1[j];
        int idx = upper_bound(t_k.begin(), t_k.end(), t_N_j_minus_1 - 1) - t_k.begin() - 1;
        ll max_e = -INF;
        if (idx >= 0) {
            max_e = prefix_max_e_k_j[j][idx];
        }
        ll t_N_j = max(e_N_j, max_e);
        t_N_j_minus_1 = t_N_j;
    }
    return t_N_j_minus_1; // Arrival time at the hotel
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccDtsAxK.o: in function `main':
grader.cpp:(.text.startup+0x43e): undefined reference to `init(int, int, std::vector<long long, std::allocator<long long> >, std::vector<int, std::allocator<int> >, int, int, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x48c): undefined reference to `arrival_time(long long)'
collect2: error: ld returned 1 exit status