#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, L;
vector<int> W, S;
int X, M;
vector<ll> T;
ll expected[1001][1001];
vector<int> tot_ord[1001];
int pos[1001][1001];
void init(int _L, int _N, std::vector<long long> _T, std::vector<int> _W, int _X, int _M, std::vector<int> _S)
{
L = _L;
M = _M;
N = _N;
T = _T;
W = _W;
X = _X;
S = _S;
// W.push_back(X);
// vector<vector<ll>> exp(N, vector<ll>(M));
vector<int> ord(N);
iota(begin(ord), end(ord), 0);
for (int i = 0; i < N; ++i) {
expected[i][0] = T[i];
}
for (int j = 1; j < M; ++j) {
sort(begin(ord), end(ord), [&](int x, int y){
if (expected[x][j - 1] != expected[y][j - 1]) return expected[x][j - 1] < expected[y][j - 1];
return W[x] < W[y];
});
tot_ord[j - 1] = ord;
ll tim = -1;
for (int it = 0; it < N; ++it) {
int i = ord[it];
pos[j - 1][i] = it;
// cerr << W[i] << " ";
expected[i][j] = expected[i][j - 1] + 1LL * W[i] * (S[j] - S[j - 1]);
expected[i][j] = max(tim, expected[i][j]);
tim = max(expected[i][j], tim);
}
// cerr << endl;
if (j == M - 1) {
sort(begin(ord), end(ord), [&](int x, int y){
if (expected[x][j - 1] != expected[y][j - 1]) return expected[x][j - 1] < expected[y][j - 1];
return W[x] < W[y];
});
tot_ord[j] = ord;
for (int it = 0; it < N; ++it) {
int i = ord[it];
pos[j][i] = it;
}
}
}
// for (int i = 0; i < M; ++i) {
// for (int j = 0; j < N; ++j) {
// cerr << tot_ord[i][j] << " ";
// }
// cerr << "\n";
// }
// cerr << "\nDone!\n";
}
bool lessi(ll e, int x, int j) {
if (e != expected[x][j]) return e < expected[x][j];
return X < W[x];
}
bool strict_less(ll e, int x, int j) {
if (e != expected[x][j]) return e < expected[x][j];
return X < W[x];
}
int get_behind(ll e, int j, vector<bool>& overtook, int pos) {
auto& ord = tot_ord[j];
for (int i = pos; i >= 0; --i) {
if (overtook[ord[i]]) continue;
if (e == expected[ord[i]][j] && X <= W[ord[i]]) {
overtook[ord[i]] = true;
continue;
}
if (e >= expected[ord[i]][j] && X < W[ord[i]]) return i;
if (e < expected[ord[i]][j] && X <= W[ord[i]]) {
overtook[ord[i]] = true;
}
}
return -1;
}
int search(ll e, int j) {
int l = 0, r = N - 1;
int res = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (lessi(e, tot_ord[mid][j], j)) {
r = mid - 1;
} else {
l = mid + 1;
res = mid;
}
}
return res;
}
long long arrival_time(long long Y)
{
vector<bool> overtook(N);
int pos = N - 1;
ll e = Y;
// cerr << Y << ":\n";
for (int i = 1; i < M; ++i) {
int front_id = get_behind(e, i - 1, overtook, pos);
pos = front_id;
// if (pos != -1) cerr << "Initial pos = " << pos << ", bus index = " << tot_ord[i - 1][pos] << "\n";
// if (strict_less(e, id, i - 1)) id -= 1;
e = e + 1LL * X * (S[i] - S[i - 1]);
// cerr << "Expected = ";
// for (int j = 0; j < N; ++j) {
// int o = tot_ord[i][j];
// cerr << expected[o][i] << " ";
// }
// cerr << " -> ";
// cerr << "Overtaken = ";
// for (int i = 0; i < N; ++i) {
// cerr << overtook[i] << " ";
// }
// cerr << "\n";
// cerr << "Initial time = " << e << " -> ";
if (front_id >= 0) {
front_id = tot_ord[i - 1][front_id];
// int id = tot_ord[i][front_id];
// cerr << id << endl;
// cerr << "at = " << front_id << " we have = " << e << ", now = ";
// cerr << id << " " << e << " " << expected[id][i] << " ?= " << strict_less(e, id, i) << endl;
e = max(e, expected[front_id][i]);
// cerr << e << "\n";
} else {
// cerr << "\n";
}
}
// cerr << Y << ":\n";
// for (int j = 0; j < M; ++j) {
// for (int i = 0; i <= N; ++i) {
// cerr << exp[i][j] << " ";
// }
// cerr << "\n";
// }
// cerr << "\n";
return e;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |