| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 847220 | I_love_Hoang_Yen | 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 "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MAX_SS = 1011;
// lines[i]: stores lines between i-th and (i+1)-th sorting stations
// each line is represented by its 2 endpoints
set<pair<ll, ll>> lines[MAX_SS];
int M;
ll X;
vector<ll> S;
void init(
int L,
int nBus, vector<ll> T, vector<int> W,
int _X,
int _M, vector<int> _S) {
M = _M;
X = _X;
S = _S;
// sort buses in decreasing order of W (so slowest buses are processed first)
vector<pair<ll, ll>> buses(nBus);
for (int i = 0; i < nBus; ++i) buses[i] = make_pair(W[i], T[i]);
std::sort(buses.begin(), buses.end());
std::reverse(buses.begin(), buses.end());
// init gaps between 2 sorting stations
for (int i = 0; i < M-1; ++i) { // only M-1 gaps
lines[i].clear();
lines[i].insert({0, 0});
}
// for each bus, add its line to all gaps
for (const auto& [w, t] : buses) {
ll cur_time = t;
for (int j = 0; j < M-1; ++j) {
auto it = std::prev(lines[j].lower_bound({cur_time, 0}));
ll exit_time = std::max(it->second, cur_time + w*(S[j+1] - S[j]));
lines[j].insert({cur_time, exit_time});
cur_time = exit_time;
}
}
}
ll arrival_time(ll Y) {
ll cur_time = Y;
for (int j = 0; j < M-1; ++j) {
auto it = std::prev(lines[j].lower_bound({cur_time, 0}));
cur_time = std::max(it->second, cur_time + X*(S[j+1] - S[j]));
}
return cur_time;
}