| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 847220 | I_love_Hoang_Yen | Overtaking (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}