#include "train.h"
#include <bits/stdc++.h>
using namespace std;
struct Departure { int idx, start, time_start; };
struct Meal { int l, r; };
struct Arrival { int time, idx; };
struct SegTree {
struct Node {
long long sum;
vector<int> *valid;
unordered_set<int> visited;
Departure dep;
int mi_time, ma_time;
int nb, ne;
Node *lc, *rc;
Node(Departure dep, long long sum, int nb, int ne)
: sum(sum), dep(dep), mi_time(dep.time_start), ma_time(dep.time_start), nb(nb), ne(ne), lc(nullptr), rc(nullptr)
{
valid = new vector<int>;
valid->push_back(dep.start);
}
Node(Node *lc, Node *rc)
: sum(lc->sum + rc->sum), mi_time(lc->mi_time), ma_time(rc->ma_time), ne(rc->ne), lc(lc), rc(rc)
{
valid = new vector<int>;
merge(lc->valid->begin(), lc->valid->end(), rc->valid->begin(), rc->valid->end(), back_inserter(*valid));
}
};
vector<Node*> roots;
Node* build(const vector<Departure> &dep, int nb, int ne) {
if (nb + 1 == ne) return new Node(dep[nb], 0, nb, ne);
Node *lc = build(dep, nb, (nb + ne) / 2);
Node *rc = build(dep, (nb + ne) / 2, ne);
return new Node(lc, rc);
}
Node* add_meal(int r, Node *node) {
if (node->ma_time < r) return node;
Node *new_node = new Node(*node);
new_node->sum++;
if (new_node->lc) {
if (node->lc->ma_time >= r) new_node->lc = add_meal(r, node->lc);
else new_node->rc = add_meal(r, node->rc);
}
return new_node;
}
void debug(Node *node, int d = 0) {
if (!node) return;
cerr << string(2 * d, ' ')
<< node << " "
<< node->sum << " ("
<< node->dep.idx << " " << node->dep.start << " " << node->dep.time_start << ") (";
for (auto x: *node->valid)
cerr << x << " ";
cerr << ")\n";
debug(node->lc, d + 1);
debug(node->rc, d + 1);
}
void debug(int root) { debug(roots[root]); }
int get_curr_root() { return roots.size() - 1; }
void add_meal(int r) { roots.push_back(add_meal(r, roots.back())); }
SegTree(const vector<Departure> &dep) { roots.push_back(build(dep, 0, dep.size())); }
};
inline bool count(vector<int> *a, int v) {
return binary_search(a->begin(), a->end(), v);
}
long long solve(
int N,
int M,
int W,
vector<int> T,
vector<int> X,
vector<int> Y,
vector<int> A,
vector<int> B,
vector<int> C,
vector<int> L,
vector<int> R
) {
int start = clock();
A.push_back(1e9 + 1);
B.push_back(1e9 + 2);
C.push_back(0);
X.push_back(N - 1);
Y.push_back(N);
M++;
vector<Departure> trains(M);
for (int i = 0; i < M; i++)
trains[i] = {i, X[i], A[i]};
vector<variant<Meal, Arrival>> events;
for (int i = 0; i < M; i++)
events.push_back(Arrival {B[i], i});
for (int i = 0; i < W; i++)
events.push_back(Meal {L[i], R[i] + 1});
sort(trains.begin(), trains.end(), [](const auto &a, const auto &b) { return a.time_start < b.time_start; });
sort(events.begin(), events.end(), [](const auto &a, const auto &b) {
int time_a, time_b;
if (holds_alternative<Meal>(a))
time_a = get<Meal>(a).l;
else
time_a = get<Arrival>(a).time;
if (holds_alternative<Meal>(b))
time_b = get<Meal>(b).l;
else
time_b = get<Arrival>(b).time;
return time_a > time_b;
});
if (clock() - start >= 0.4 * CLOCKS_PER_SEC) return 0;
SegTree segtree(trains);
vector<int> roots(M);
for (auto event: events) {
if (holds_alternative<Meal>(event)) {
Meal meal = get<Meal>(event);
segtree.add_meal(meal.r);
} else {
Arrival arrival = get<Arrival>(event);
roots[arrival.idx] = segtree.get_curr_root();
}
}
priority_queue<
tuple<long long, SegTree::Node*, int>,
vector<tuple<long long, SegTree::Node*, int>>,
greater<tuple<long long, SegTree::Node*, int>>
> q;
// add fake arrival to first node
Y.push_back(0);
B.push_back(0);
q.emplace(0, segtree.roots.back(), M);
//segtree.debug(segtree.get_curr_root());
while (!q.empty()) {
auto [d, node, arr] = q.top(); q.pop();
//cerr << d << " " << node << " " << arr << endl;
if (Y[arr] == N) return d;
if (node->visited.count(arr)) continue;
node->visited.insert(arr);
if (node->ma_time < B[arr]) continue;
if (!node->lc) {
int idx = node->dep.idx;
long long cost = T[Y[arr]] * node->sum + C[idx];
SegTree::Node *next = segtree.roots[roots[idx]];
q.emplace(d + cost, next, idx);
} else if (node->lc->ma_time >= B[arr]) {
if (count(node->lc->valid, Y[arr])) q.emplace(d, node->lc, arr);
if (count(node->rc->valid, Y[arr])) q.emplace(d + T[Y[arr]] * node->lc->sum, node->rc, arr);
} else if (node->rc->ma_time >= B[arr]) {
if (count(node->rc->valid, Y[arr])) q.emplace(d + T[Y[arr]] * node->lc->sum, node->rc, arr);
}
}
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1116 KB |
Correct. |
| 2 |
Correct |
1 ms |
828 KB |
Correct. |
| 3 |
Correct |
1 ms |
1116 KB |
Correct. |
| 4 |
Correct |
3 ms |
1116 KB |
Correct. |
| 5 |
Incorrect |
0 ms |
344 KB |
Wrong Answer. |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
57352 KB |
Correct. |
| 2 |
Correct |
105 ms |
58396 KB |
Correct. |
| 3 |
Incorrect |
0 ms |
344 KB |
Wrong Answer. |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
57352 KB |
Correct. |
| 2 |
Correct |
105 ms |
58396 KB |
Correct. |
| 3 |
Incorrect |
0 ms |
344 KB |
Wrong Answer. |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1116 KB |
Correct. |
| 2 |
Correct |
1 ms |
828 KB |
Correct. |
| 3 |
Correct |
1 ms |
1116 KB |
Correct. |
| 4 |
Correct |
3 ms |
1116 KB |
Correct. |
| 5 |
Incorrect |
0 ms |
344 KB |
Wrong Answer. |
| 6 |
Halted |
0 ms |
0 KB |
- |
