| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 849300 | Muaath_5 | 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.
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const ll N = 1005, INF = 7e15;
ll n, m, l, x;
ll pos[N][N];
ll full[N][N];
vector<int> srt[N];
vector<int> spd;
vector<ll> st;
vector<int> len;
vector<int> lmt2[N];
ll tmp;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
n = N, m = M, l = L, x = X, spd = W, st = T, len = S;
for (int j = 0; j < n; j++) {
pos[0][j] = T[j];
//full[0][j] = T[j];
srt[0].push_back(j);
}
sort(srt[0].begin(), srt[0].end(), [](int x, int y) {
return st[x] == st[y] ? spd[x] < spd[y] : st[x] < st[y];
});
for (int i = 0; i < m-1; i++) {
//cerr << "Station " << i + 1 << '\n';
pos[i + 1][srt[i][0]] = 1ll * spd[srt[i][0]] * (len[i + 1] - len[i]) + pos[i][srt[i][0]];
//full[i + 1][srt[i][0]] = 1ll * spd[srt[i][0]] * (len[i + 1] - len[i]) + full[i][srt[i][0]];
srt[i + 1].push_back(0);
//cerr << "Bus " << srt[i][0] << " Arrives " << pos[i+1][srt[i][0]] << '\n';
for (int j = 1; j < n; j++) {
srt[i + 1].push_back(j);
//full[i + 1][srt[i][j]] = 1ll * spd[srt[i][j]] * (len[i + 1] - len[i]) + full[i][srt[i][j]];
const ll exp = 1ll * spd[srt[i][j]] * (len[i + 1] - len[i]) + pos[i][srt[i][j]];
if (exp < pos[i + 1][srt[i][j - 1]]) {
pos[i + 1][srt[i][j]] = pos[i + 1][srt[i][j - 1]];
//cerr << "Intersects: ";
}
else {
pos[i + 1][srt[i][j]] = exp;
}
//cerr << "Bus " << srt[i][j] << " Arrives " << pos[i + 1][srt[i][j]] << '\n';
}
tmp = i+1;
sort(srt[i+1].begin(), srt[i+1].end(), [](int x, int y) {
return pos[tmp][x] == pos[tmp][y] ? spd[x] < spd[y] : pos[tmp][x] < pos[tmp][y];
});
}
/*
for (int i = 0; i < n; i++) {
if (spd[i] > x) {
lmt.push_back(i);
}
}
*/
}
ll arrival_time(ll Y) {
ll tm = Y;
int idx = 0;
for (int i = 0; i < m-1; i++) {
const ll exp = 1ll * x * (len[i + 1] - len[i]) + tm;
if (pos[i][srt[i][0]] >= tm) {
tm = exp;
}
else {
int l = 0, r = n - 1;
while (l < r) {
const int md = (l + r + 1) / 2;
if (pos[i][srt[i][md]] < tm || (pos[i][srt[i][md]] == tm && spd[srt[i][md]] < x))
l = md;
else
r = md - 1;
}
int prv = srt[i][l];
if (exp < pos[i + 1][prv]) {
tm = pos[i + 1][prv];
}
else {
tm = exp;
}
}
}
return tm;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init(6, 4, { 20, 10, 40, 0 }, { 5, 20, 20, 30 }, 10, 4, { 0, 1, 3, 6 });
//init(6, 2, { 10, 20 }, { 5, 3 }, 2, 2, { 0, 6 });
while (1) {
ll x;
cin >> x;
cout << arrival_time(x) << '\n';
}
}