| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1094205 | Lechaa09 | Overtaking (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
}