#include "train.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>
#include <string.h>
#define ff first
#define ss second
using namespace std;
constexpr int capacity = 5e6;
int ptr = 0;
struct Node {int val, lc, rc;};
Node st[capacity];
struct PersistentSegmentTree {
int n;
int root = 0;
PersistentSegmentTree() {}
PersistentSegmentTree(int _n) : n(_n), root(0) {}
void reset() {memset(st, 0, sizeof(st)); ptr = 1; root = 0;}
int copy_node(int rt) {st[ptr] = st[rt]; return ptr++;}
int modify(int qi, int qx) {return root = modify(qi, qx, 0, n-1, root);}
int modify(int qi, int qx, int l, int r, int rt) {
rt = copy_node(rt);
if (l == r) {
st[rt].val += qx;
return rt;
}
int m = l + r >> 1;
auto &[val, lc, rc] = st[rt];
if (qi <= m) {
lc = modify(qi, qx, l, m, lc);
}else{
rc = modify(qi, qx, m+1, r, rc);
}
val = st[lc].val + st[rc].val;
return rt;
}
int query(int ql, int qr, int root) {return query(ql, qr, 0, n-1, root);}
int query(int ql, int qr, int l, int r, int rt) {
if (rt == 0) return 0;
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return st[rt].val;
int m = l + r >> 1;
auto &[val, lc, rc] = st[rt];
return (
query(ql, qr, l, m, lc) +
query(ql, qr, m+1, r, rc)
);
}
};
struct DataStructure {
int n;
PersistentSegmentTree st;
vector<int> root;
DataStructure(int _n, vector<pair<int, int>> seg) : n(_n), st(_n) {
st.reset();
vector<vector<int>> table(n);
for (auto [l, r]: seg) table[r].push_back(l);
int rt = 0;
for (int r=0; r<n; r++) {
for (int l: table[r]) rt = st.modify(l, +1);
root.push_back(rt);
}
}
int query(int ql, int qr) {
if (ql > qr) return 0;
return st.query(ql, n-1, root[qr]);
}
};
long long solve(int n, int m, int w, std::vector<int> t, std::vector<int> x, std::vector<int> y,
std::vector<int> a, std::vector<int> b, std::vector<int> c, std::vector<int> l,
std::vector<int> r)
{
// relabeling timeline
int z = 0;
{
vector<int> tb;
tb.reserve(m*2 + w*2 + 10);
for (int &i: a) tb.push_back(i);
for (int &i: b) tb.push_back(i);
for (int &i: l) tb.push_back(i);
for (int &i: r) tb.push_back(i);
tb.push_back(-1);
tb.push_back(1e9+1);
sort(tb.begin(), tb.end());
tb.erase(unique(tb.begin(), tb.end()), tb.end());
auto get_id = [&] (int i) -> int {return lower_bound(tb.begin(), tb.end(), i) - tb.begin();};
for (int &i: a) i = get_id(i);
for (int &i: b) i = get_id(i);
for (int &i: l) i = get_id(i);
for (int &i: r) i = get_id(i);
z = tb.size();
}
vector<pair<int, int>> lr(w);
for (int i=0; i<w; i++) lr[i] = {l[i], r[i]};
DataStructure ds(z, lr);
// debug
// {
// cout << "cost:\t"; for (int i: t) cout << i << " "; cout << "\n";
// cout << "edge:\n";
// for (int i=0; i<m; i++) cout << x[i] << " -> " << y[i] << ": " << c[i] << " -- [" << a[i] << " ~ " << b[i] << "]\n";
// cout << "meal:\n";
// for (int i=0; i<w; i++) cout << "[" << l[i] << " ~ " << r[i] << "]\n";
// cout << "\n\ncount: \n";
// for (int i=0; i<z; i++) {
// for (int j=0; j<z; j++) {
// cout << (j < i ? 0 : ds.query(i, j)) << " ";
// }
// cout << "\n";
// }
// cout << "\n\n";
// }
vector<pair<int, int>> ev;
ev.reserve(m*2 + 10);
for (int i=0; i<m; i++) {
ev.push_back({i, +1});
ev.push_back({i, -1});
}
sort(ev.begin(), ev.end(), [&] (pair<int, int> x, pair<int, int> y) -> bool {
int tx = x.ss == 1 ? b[x.ff] : a[x.ff];
int ty = y.ss == 1 ? b[y.ff] : a[y.ff];
if (tx == ty) return x.ss > y.ss;
return tx < ty;
});
// Object: {cost, arrival_time, opt_left, opt_right}
struct DequeObject {int id, l, r;};
vector<long long> dp(m);
vector<deque<DequeObject>> dq(n);
// first
{a.push_back(0);
b.push_back(0);
c.push_back(0);
x.push_back(0);
y.push_back(0);
dp.push_back(0);}
// last
{a.push_back(z-1);
b.push_back(z-1);
c.push_back(0);
x.push_back(n-1);
y.push_back(n-1);
dp.push_back(0);}
auto calc_cost = [&] (int frm, int departure) -> long long {
int v = y[frm];
int arrival = b[frm];
long long meal = t[v];
if (arrival > departure) return 1e18;
long long cnt = ds.query(arrival + 1, departure - 1);
return dp[frm] + cnt * meal;
};
auto compare_moment = [&] (int frm1, int frm2, int departure) -> bool {
return calc_cost(frm1, departure) < calc_cost(frm2, departure);
// long long c1 = calc_cost(frm1, departure);
// long long c2 = calc_cost(frm2, departure);
// if (frm1 == 4 && frm2 == 0) {
// cout << "at " << departure << ": " << c1 << " v.s. " << c2 << "\n";
// }
// return c1 < c2;
};
auto insert_object = [&] (deque<DequeObject> &dq, int id) -> void {
while (dq.size() && compare_moment(id, dq.back().id, dq.back().l)) {
dq.pop_back();
}
int arrival = b[id];
if (dq.size()) {
int l = max(arrival - 1, dq.back().l);
int r = dq.back().r + 1;
// if (id == 4) cout << dq.back().id << ": " << l << " ~ " << r << " rival\n";
while (l+1 < r) {
int m = l + r >> 1;
if (compare_moment(id, dq.back().id, m)) {
r = m;
}else{
l = m;
}
}
dq.back().r = l;
if (l+1 <= z-1) {
dq.push_back({id, l+1, z-1});
}
}else{
if (arrival <= z-1) {
dq.push_back({id, arrival, z-1});
}
}
};
auto find_best = [&] (deque<DequeObject> &dq, int go) -> long long {
int u = x[go];
int departure = a[go];
while (dq.size() && dq.front().r < departure) dq.pop_front();
if (!dq.size()) return 1e18;
return calc_cost(dq.front().id, departure);
};
insert_object(dq[0], m);
for (auto [id, ty]: ev) {
if (ty == +1) {
int v = y[id];
insert_object(dq[v], id);
}else{
int u = x[id];
dp[id] = find_best(dq[u], id) + c[id];
}
}
// cout << "dp:\t";
// for (long long i: dp) cout << i << " "; cout << "\n";
long long ans = find_best(dq[n-1], m+1);
return ans;
}
