#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;
#define en(x) (x).end()
#define bg(x) (x).begin()
#define all(x) bg(x), en(x)
#define sz(x) int(x.size())
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define each(a, x) for (auto &a : x)
using pi = pair<int, int>;
struct Point {
int x, y, id;
Point() {};
Point(int X, int Y, int ID) : x(X), y(Y), id(ID) {};
const bool operator<(const Point &other) const {
if (x == other.x && y == other.y) return id < other.id;
if (x == other.x) return y < other.y;
return x < other.x;
}
int dist(Point &other) {
return abs(other.x - x) + abs(other.y - y);
}
};
struct Edge {
int u, v, dist;
};
struct Line {
int x, y, h;
};
int pid = 0;
int n, m;
ll min_distance(vi X, vi H, vi L, vi R, vi Y, int s, int g) {
n = sz(X); m = sz(L);
vi nid(n), eid(m); iota(all(nid), 0); iota(all(eid), 0);
sort(all(nid), [&](int a, int b) {return X[a] < X[b];});
sort(all(eid), [&](int a, int b) {
if (L[a] == L[b] && R[a] == R[b]) return Y[a] < Y[b];
if (L[a] == L[b]) return X[R[a]] < X[R[b]];
return X[L[a]] < X[L[b]];
});
vvi eadj(m, vi()), badj(n, vi());
vector<Edge> edges; vector<Point> points;
FOR(i, 0, m) {
FOR(j, 0, n) {
if (X[j] < X[L[i]]) continue;
if (X[j] > X[R[i]]) continue;
if (H[j] < Y[i]) continue;
int id = pid++;
points.push_back(Point{X[j], Y[i], id});
eadj[i].pb(id);
badj[j].pb(id);
}
sort(all(eadj[i]), [&](int a, int b) {return points[a] < points[b];});
FOR(j, 0, sz(eadj[i]) - 1) {
edges.pb(Edge{eadj[i][j], eadj[i][j+1], points[eadj[i][j]].dist(points[eadj[i][j+1]])});
}
}
FOR(i, 0, n) {
points.pb(Point(X[i], 0, pid++));
points.pb(Point(X[i], H[i], pid++));
badj[i].pb(pid-2); badj[i].pb(pid-1);
sort(all(badj[i]), [&](int a, int b) {return points[a] < points[b];});
FOR(j, 0, sz(badj[i]) - 1) {
edges.pb(Edge{badj[i][j], badj[i][j+1], points[badj[i][j]].dist(points[badj[i][j+1]])});
}
}
int sid = badj[s][0], gid = badj[g][0];
vvi padj(sz(points), vi());
for (auto &el : edges) {
padj[el.u].pb(el.v);
padj[el.v].pb(el.u);
}
int np = sz(points);
const ll INF = 4e18;
vector<ll> dist(np, INF), par(np, -1);
dist[sid] = 0;
using pl = pair<ll, ll>;
priority_queue<pl, vector<pl>, greater<pl>> pq;
pq.push({0, sid});
while (!pq.empty()) {
int cur = pq.top().second;
ll d = pq.top().first;
pq.pop();
for (auto &v : padj[cur]) {
if (d + points[cur].dist(points[v]) < dist[v]) {
dist[v] = d + points[cur].dist(points[v]);
par[v] = cur;
pq.push({dist[v], v});
}
}
}
// vi path; int cur = gid;
// while (cur != -1) {
// path.pb(cur);
// cur = par[cur];
// }
// reverse(all(path));
// for (auto &el : path) {
// cout << points[el].x << " " << points[el].y << "\n";
// }
return dist[gid];
}
