// 65 marks
#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long // remove when necessary
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 1001;
int arrive[mxN][mxN]; // [position][car]
int n, m;
int w[mxN], s[mxN];
int x;
map<int, int> mp[mxN];
map<int, int>::iterator it;
void reset() {
for (int i = 0; i < n; i++) w[i] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) arrive[i][j] = 0;
s[i] = 0;
mp[i].clear();
}
}
void CalcArrival() {
for (int i = 1; i < m; i++) {
// calculate estimated ending time
for (int j = 0; j < n; j++) {
arrive[i][j] = arrive[i - 1][j] + w[j] * (s[i] - s[i - 1]);
// cerr << arrive[i - 1][j] << " | " << w[j] << " | ";
// cerr << s[i] - s[i - 1] << endl;
// cerr << i << " " << j << ": " << arrive[i][j] << endl;
}
// "delay" faster cars
// // brute force method
// for (int j = 0; j < n; j++) {
// for (int k = 0; k < n; k++) {
// if (j == k) continue;
// if (arrive[i - 1][j] > arrive[i - 1][k] && arrive[i][j] < arrive[i][k]) {
// // j overtook k on the road, delay
// arrive[i][j] = arrive[i][k];
// }
// }
// }
// sort by (estimated) ending time
vector<pair<pii, int>> v;
for (int j = 0; j < n; j++) {
v.pb({{arrive[i][j], arrive[i - 1][j]}, j});
}
sort(v.begin(), v.end(), [&](pair<pii, int> &lhs, pair<pii, int> &rhs) {
// sort by larger arrival time
if (lhs.ff.ff != rhs.ff.ff) return lhs.ff.ff > rhs.ff.ff;
// tiebreak by smaller starting time
return lhs.ff.ss < rhs.ff.ss;
});
for (pair<pii, int> &cur : v) {
it = mp[i].lower_bound(cur.ff.ss);
if (it == mp[i].begin()) {
if (it->ff != cur.ff.ss) mp[i][cur.ff.ss] = cur.ff.ff;
} else {
--it;
arrive[i][cur.ss] = it->ss;
}
}
mp[i].clear();
v.clear();
for (int j = 0; j < n; j++) {
v.pb({{arrive[i - 1][j], arrive[i][j]}, j});
}
sort(v.begin(), v.end(), [&](pair<pii, int> &lhs, pair<pii, int> &rhs) {
// sort by smaller starting time
if (lhs.ff.ff != rhs.ff.ff) return lhs.ff.ff < rhs.ff.ff;
// tiebreak by larger arrival time
return lhs.ff.ss > rhs.ff.ss;
});
int curmax = -1;
for (pair<pii, int> &cur : v) {
if (cur.ff.ss > curmax) {
mp[i][cur.ff.ff] = cur.ff.ss;
curmax = cur.ff.ss;
}
}
}
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < n; j++) {
// cerr << arrive[i][j] << ' ';
// }
// cerr << endl;
// }
}
void init(int32_t L, int32_t N, vector<long long> T, vector<int32_t> W, int32_t X, int32_t M, vector<int32_t> S)
{
n = N; m = M;
reset();
for (int i = 0; i < n; i++) {
arrive[0][i] = T[i]; w[i] = W[i];
}
for (int i = 0; i < m; i++) {
s[i] = S[i];
}
x = X;
CalcArrival();
}
long long bruh_arrival_time(long long t)
{
for (int i = 1; i < m; i++) {
int nt2 = t + x * (s[i] - s[i - 1]);
for (int j = 0; j < n; j++) {
// look for delay
if (t > arrive[i - 1][j]) {
nt2 = max(nt2, arrive[i][j]);
}
}
t = nt2;
}
return t;
}
long long arrival_time(long long t)
{
// return bruh_arrival_time(t);
for (int i = 1; i < m; i++) {
int nt1 = t + x * (s[i] - s[i - 1]);
// look for delay
it = mp[i].lower_bound(t);
if (it != mp[i].begin()) {
--it;
nt1 = max(nt1, it->ss);
}
t = nt1;
}
return t;
}
#undef int
Compilation message
fish.cpp:3:10: fatal error: overtaking.h: No such file or directory
3 | #include "overtaking.h"
| ^~~~~~~~~~~~~~
compilation terminated.
