#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include "train.h"
using namespace std;
const long long INF = 1e18;
// --- Persistent Segment Tree ---
struct Node {
int sum;
int l_child, r_child;
};
vector<Node> tree;
vector<int> roots;
int insert(int prev_root, int l, int r, int val) {
int cur = tree.size();
tree.push_back(tree[prev_root]); // Copy previous node
tree[cur].sum++;
if (l == r) return cur;
int mid = l + (r - l) / 2;
if (val <= mid) {
tree[cur].l_child = insert(tree[prev_root].l_child, l, mid, val);
} else {
tree[cur].r_child = insert(tree[prev_root].r_child, mid + 1, r, val);
}
return cur;
}
int query(int node, int l, int r, int ql, int qr) {
if (!node || ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return tree[node].sum;
int mid = l + (r - l) / 2;
return query(tree[node].l_child, l, mid, ql, qr) +
query(tree[node].r_child, mid + 1, r, ql, qr);
}
// --- Problem State Structs ---
struct Train {
int id, X, Y, A, B;
long long C;
};
struct DequeElement {
int train_id;
int start_time; // The compressed time when this train becomes optimal
};
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) {
// 1. Coordinate Compression for Time
vector<int> times = {0}; // Time 0 is our starting dummy time
for (int i = 0; i < M; i++) {
times.push_back(A[i]);
times.push_back(B[i]);
}
for (int i = 0; i < W; i++) {
times.push_back(L[i]);
times.push_back(R[i]);
}
sort(times.begin(), times.end());
times.erase(unique(times.begin(), times.end()), times.end());
int K = times.size(); // Max compressed time
auto get_time = [&](int t) {
return lower_bound(times.begin(), times.end(), t) - times.begin() + 1;
};
// 2. Build Persistent Segment Tree
tree.push_back({0, 0, 0}); // Dummy 0 node
roots.assign(K + 2, 0);
vector<vector<int>> meals_at_L(K + 2);
for (int i = 0; i < W; i++) {
meals_at_L[get_time(L[i])].push_back(get_time(R[i]));
}
// Build roots backwards so root[t] contains all meals with L_i >= t
for (int t = K; t >= 1; t--) {
roots[t] = roots[t + 1];
for (int r_val : meals_at_L[t]) {
roots[t] = insert(roots[t], 1, K, r_val);
}
}
// Cost function: DP[u] + wait cost at planet p from B[u] to current_time
vector<long long> dp(M + 1, INF);
vector<int> train_B(M + 1, 0); // Stores compressed arrival time for each train
auto get_wait_cost = [&](int u, int current_time, int p) {
if (dp[u] == INF) return INF;
int b_time = train_B[u];
// Query meals strictly inside [b_time, current_time]
int meals = query(roots[b_time], 1, K, 1, current_time);
return dp[u] + 1LL * T[p] * meals;
};
// 3. Deque Optimization Binary Search
// Finds the earliest time t in [B[w], K] where w is better than u
auto find_intersection = [&](int u, int w, int p) {
int low = train_B[w], high = K, ans = K + 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (get_wait_cost(w, mid, p) <= get_wait_cost(u, mid, p)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
};
// 4. Sort Events
vector<vector<Train>> arrivals(K + 2);
vector<vector<Train>> departures(K + 2);
for (int i = 0; i < M; i++) {
Train t = {i + 1, X[i], Y[i], get_time(A[i]), get_time(B[i]), C[i]};
departures[t.A].push_back(t);
arrivals[t.B].push_back(t);
}
// 5. Setup DP and Deques
vector<deque<DequeElement>> dq(N);
// Dummy Train 0 arriving at Planet 0 at Time 1 (compressed time 0 is index 1)
dp[0] = 0;
train_B[0] = 1;
dq[0].push_back({0, 1});
// 6. Sweepline execution
for (int t = 1; t <= K; t++) {
// A. Process all arrivals at time t
for (const Train& train : arrivals[t]) {
int u = train.id;
int p = train.Y;
train_B[u] = t;
if (dp[u] == INF) continue;
while (!dq[p].empty()) {
int back_u = dq[p].back().train_id;
int start_t = dq[p].back().start_time;
if (get_wait_cost(u, start_t, p) <= get_wait_cost(back_u, start_t, p)) {
dq[p].pop_back(); // u is better or equal at the time back_u became active
} else {
break;
}
}
if (dq[p].empty()) {
dq[p].push_back({u, t});
} else {
int back_u = dq[p].back().train_id;
int intersect = find_intersection(back_u, u, p);
if (intersect <= K) {
dq[p].push_back({u, intersect});
}
}
}
// B. Process all departures at time t
for (const Train& train : departures[t]) {
int v = train.id;
int p = train.X;
// Pop suboptimal trains from the front of the deque
while (dq[p].size() > 1 && dq[p][1].start_time <= t) {
dq[p].pop_front();
}
if (!dq[p].empty()) {
int opt_u = dq[p].front().train_id;
long long wait_cost = get_wait_cost(opt_u, t, p);
if (wait_cost != INF) {
dp[v] = wait_cost + train.C;
}
}
}
}
// 7. Find the Answer
long long ans = INF;
for (int t = 1; t <= K; t++) {
for (const Train& train : arrivals[t]) {
if (train.Y == N - 1 && dp[train.id] != INF) {
// Add the cost of waiting from arrival to the end of time (K)
ans = min(ans, get_wait_cost(train.id, K, N - 1));
}
}
}
return ans == INF ? -1 : ans;
}
