#include "bits/extc++.h"
using namespace std;
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
using ll = long long;
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
return out << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
struct Comp {
map<T, int> mp;
int operator()(const T& t) {
auto [it, inserted] = mp.emplace(t, -1);
if (inserted) {
it->second = sz(mp) - 1;
}
return it->second;
}
};
template <typename S>
long dijkstra(const vector<tuple<S, S, long>>& edges, S src, S dest) {
dbg("A");
int n = 2 * sz(edges) + 10;
Comp<S> comp;
vector<pair<int, long>> graph[n];
for (auto& [u, v, w] : edges) {
int cu = comp(u), cv = comp(v);
graph[cu].emplace_back(cv, w);
graph[cv].emplace_back(cu, w);
}
long dist[n];
memset(dist, 0x3f, sizeof(dist));
min_pq<pair<long, int>> pq;
auto push = [&](int u, long d) -> void {
if (d >= dist[u]) {
return;
}
dist[u] = d;
pq.emplace(d, u);
};
int c_src = comp(src), c_dest = comp(dest);
push(c_src, 0);
while (sz(pq)) {
auto [d, u] = pq.top();
pq.pop();
if (u == c_dest) {
return d;
}
if (d != dist[u]) {
continue;
}
for (auto& [v, w] : graph[u]) {
push(v, d + w);
}
}
return -1;
}
namespace s1 {
long solve(vector<pair<int, int>> arr,
vector<array<int, 3>> walk,
int src,
int dest) {
src = arr[src].first;
dest = arr[dest].first;
map<int, vector<pair<int, int>>> evts;
for (auto& [x, h] : arr) {
evts[-h].emplace_back(x, -1);
}
for (auto& [ql, qr, h] : walk) {
ql = arr[ql].first;
qr = arr[qr].first;
evts[-h].emplace_back(ql, qr);
}
vector<array<int, 3>> d_walk;
{
set<int> pos;
for (auto& [nh, ev] : evts) {
int h = -nh;
for (auto& [x, ty] : ev) {
if (ty == -1) {
dbg(h, x);
pos.insert(x);
}
}
for (auto& [ql, qr] : ev) {
if (qr == -1) {
continue;
}
dbg(h, ql, qr);
auto it = pos.lower_bound(ql);
while (true) {
int cl = *it;
++it;
int cr = *it;
d_walk.push_back({cl, cr, h});
dbg("A", *it, qr);
assert(*it <= qr);
if (*it == qr) {
break;
}
}
}
}
}
for (auto& [ql, qr, h] : d_walk) {
dbg(ql, qr, h);
}
using S = pair<int, int>;
S s_src {src, 0}, s_dest {dest, 0};
vector<S> states {s_src, s_dest};
for (auto& [ql, qr, h] : d_walk) {
states.emplace_back(ql, h);
states.emplace_back(qr, h);
}
sort(begin(states), end(states));
states.erase(unique(begin(states), end(states)), states.end());
map<int, vector<int>> buildings;
for (auto& [x, y] : states) {
buildings[x].push_back(y);
}
vector<tuple<S, S, long>> edges;
for (auto& [x, ys] : buildings) {
sort(begin(ys), end(ys));
for (int i = 0; i + 1 < sz(ys); i++) {
edges.emplace_back(S(x, ys[i]), S(x, ys[i + 1]), ys[i + 1] - ys[i]);
}
}
for (auto& [ql, qr, h] : d_walk) {
edges.emplace_back(S(ql, h), S(qr, h), qr - ql);
}
for (auto& [u, v, w] : edges) {
dbg(u, v, w);
}
return dijkstra(edges, s_src, s_dest);
}
} // namespace s1
ll min_distance(vector<int> arr_x,
vector<int> arr_h,
vector<int> walk_l,
vector<int> walk_r,
vector<int> walk_y,
int src,
int dest) {
int n = sz(arr_x), m = sz(walk_l);
vector<pair<int, int>> arr(n);
for (int i = 0; i < n; i++) {
arr[i] = {arr_x[i], arr_h[i]};
}
vector<array<int, 3>> walk(m);
for (int i = 0; i < m; i++) {
walk[i] = {walk_l[i], walk_r[i], walk_y[i]};
}
return s1::solve(arr, walk, src, dest);
}
