| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1038987 | Zicrus | 추월 (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
typedef unsigned long long ll;
vector<vector<ll>> tCur, tNxt;
vector<ll> s;
ll x, m;
void init(int l, int n, vector<ll> t, vector<int> w, int x1, int m1, vector<int> s1) {
s = vector<ll>(s1.size());
for (int i = 0; i < s1.size(); i++) s[i] = s1[i];
m = m1;
x = x1;
tCur = vector<vector<ll>>(m-1);
tNxt = vector<vector<ll>>(m-1);
vector<pair<ll, ll>> busses(n);
for (int i = 0; i < n; i++) {
busses[i] = {t[i], w[i]};
}
sort(busses.begin(), busses.end());
for (int t = 0; t < m-1; t++) {
for (int i = 0; i < n; i++) {
ll curTime = busses[i].first;
if (t > 0) {
ll idealNxt = curTime + busses[i].second * (s[t] - s[t-1]);
auto iter = lower_bound(tCur[t-1].begin(), tCur[t-1].end(), curTime);
ll id = iter - tCur[t-1].begin();
ll mxNxt = id > 0 ? tNxt[t-1][id-1] : 0;
busses[i].first = curTime = max(idealNxt, mxNxt);
}
ll idealNxt = curTime + busses[i].second * (s[t+1] - s[t]);
auto iter = lower_bound(tCur[t].begin(), tCur[t].end(), curTime);
ll id = iter - tCur[t].begin();
ll mxNxt = id > 0 ? tNxt[t][id-1] : 0;
ll nxt = max(idealNxt, mxNxt);
if (nxt > mxNxt) {
if (id < tCur[t].size() && curTime == tCur[t][id]) {
tNxt[t][id] = nxt;
}
else {
auto iter2 = upper_bound(tNxt[t].begin(), tNxt[t].end(), nxt);
tCur[t].erase(iter, tCur[t].begin() + (iter2 - tNxt[t].begin()));
tNxt[t].erase(tNxt[t].begin() + id, iter2);
tCur[t].insert(iter, curTime);
tNxt[t].insert(tNxt[t].begin() + id, nxt);
}
}
}
}
}
ll arrival_time(ll y) {
for (int t = 0; t < m-1; t++) {
ll idealNxt = y + x * (s[t+1] - s[t]);
ll id = lower_bound(tCur[t].begin(), tCur[t].end(), y) - tCur[t].begin();
ll mxNxt = id > 0 ? tNxt[t][id-1] : 0;
y = max(idealNxt, mxNxt);
}
return y;
}