#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;
using pl = pair<ll, 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 Event {
int x, id; bool walk, first;
const bool operator<(const Event &other) const {
if (x != other.x) return x < other.x;
auto rank = [](bool walk, bool first) {
if (walk && first) return 0;
if (!walk) return 1;
return 2;
};
int r1 = rank(walk, first), r2 = rank(other.walk, other.first);
if (r1 != r2) return r1 < r2;
if (id != other.id) return id < other.id;
if (walk != other.walk) return walk < other.walk;
if (first != other.first) return first > other.first;
return false;
}
};
const ll INF = 4e18;
int n, m, np, pid = 0;
int s, g;
vi X, H, L, R, Y, nid, eid;
vvi eadj, badj, padj;
vector<Edge> edges;
vector<Point> points;
void preprocess() {
nid.resize(n), eid.resize(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]];
});
badj.resize(n), eadj.resize(m);
vector<Event> events; FOR(i, 0, m) events.pb(Event({X[L[i]], i, true, true})), events.pb(Event{X[R[i]], i, true, false});
FOR(i, 0, n) events.pb(Event{X[i], i, false, false});
sort(all(events));
set<pi> active;
each(evt, events) {
if (evt.walk) {
if (evt.first) {
active.insert({Y[evt.id], evt.id});
} else {
active.erase({Y[evt.id], evt.id});
}
} else {
auto itend = active.lower_bound({H[evt.id] + 1, INT_MIN});
for (auto it = active.begin(); it != itend; ++it) {
int id = pid++;
int i = it->second, j = evt.id;
points.push_back(Point{X[j], Y[i], id});
eadj[i].pb(id);
badj[j].pb(id);
}
}
}
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]])});
}
}
np = sz(points);
padj.assign(np, vi());
for (auto &el : edges) {
padj[el.u].pb(el.v);
padj[el.v].pb(el.u);
}
}
void dijkstra(int root, vector<ll> &dist, vi &par) {
dist.assign(np, INF); par.assign(np, -1);
dist[root] = 0;
priority_queue<pl, vector<pl>, greater<pl>> pq;
pq.push({0, root});
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});
}
}
}
}
void output_path(int gid, vi &par) {
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";
}
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int S, int G) {
X = x; H = h; L = l; R = r; Y = y; s = S; g = G;
n = sz(X); m = sz(L);
preprocess();
int sid = badj[s][0], gid = badj[g][0];
vector<ll> dist; vi par;
dijkstra(sid, dist, par);
// output_path(gid, par);
return dist[gid] == INF ? -1 : dist[gid];
}
