#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) ((signed)a.size())
using ll = long long;
template <class T>
using min_heap = priority_queue <T, vector <T>, greater <T>>;
const int N = 1e5 + 5;
struct building{
int x, h;
int idx;
friend bool operator< (const building& lhs, const building& rhs){
return lhs.h < rhs.h;
}
};
struct skywalk{
int l, r, y;
int idx;
friend bool operator< (const skywalk& lhs, const skywalk& rhs){
return lhs.y < rhs.y;
}
};
int n, m;
building a[N];
skywalk b[N];
int s, t;
namespace subtask12{
bool check(){
return true;
}
vector <vector <int>> pos_y;
vector <map <int, vector <pair <int, int>>>> adj;
vector <map <int, ll>> dist;
min_heap <tuple <ll, int, int>> pq;
void transition(ll d, int x, int y){
auto itr = dist[x].find(y);
if (itr == dist[x].end()){
dist[x][y] = d;
pq.emplace(d, x, y);
}
else if (itr->second > d){
itr->second = d;
pq.emplace(d, x, y);
}
}
ll solve(){
pos_y.resize(n);
pos_y[s].emplace_back(0);
pos_y[t].emplace_back(0);
adj.resize(n);
dist.resize(n);
{
set <int> alive;
for (int i = 0; i < n; i++){
alive.emplace(i);
}
int ib = 0;
vector <building> sa(a, a + n);
sort(sa.begin(), sa.end());
for (auto &[x, h, ia]: sa){
while (ib < m and b[ib].y <= h){
auto itr = alive.lower_bound(b[ib].l);
int pre = -1;
while (itr != alive.end() and *itr <= b[ib].r){
if (not pos_y[*itr].empty()){
auto u = pair{*itr, pos_y[*itr].back()}, v = pair{*itr, b[ib].y};
adj[u.first][u.second].emplace_back(v);
adj[v.first][v.second].emplace_back(u);
}
pos_y[*itr].emplace_back(b[ib].y);
if (pre != -1){
auto u = pair{pre, b[ib].y}, v = pair{*itr, b[ib].y};
adj[u.first][u.second].emplace_back(v);
adj[v.first][v.second].emplace_back(u);
}
pre = *itr;
itr++;
}
ib++;
}
alive.erase(ia);
}
}
transition(0ll, s, 0);
while (not pq.empty()){
auto [d, x, y] = pq.top(); pq.pop();
if (d > dist[x][y]){
continue;
}
if (x == t and y == 0){
return d;
}
for (auto [tx, ty]: adj[x][y]){
ll td = d + (abs(a[x].x - a[tx].x) + abs(y - ty));
transition(td, tx, ty);
}
}
return -1;
}
}
ll min_distance(vector <int> _x, vector <int> _h, vector <int> _l, vector <int> _r, vector <int> _y, int _s, int _t){
n = isz(_x); m = isz(_l);
for (int i = 0; i < n; i++){
int x = _x[i], h = _h[i];
a[i] = building{x, h, i};
}
for (int i = 0; i < m; i++){
int l = _l[i], r = _r[i], y = _y[i];
b[i] = skywalk{l, r, y, i};
}
sort(b, b + m);
s = _s; t = _t;
if (subtask12::check()){
return subtask12::solve();
}
}
