#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
typedef long long ll;
const ll INF = 1e18;
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int start, int goal) {
int n = (int)X.size(), m = (int)L.size();
vector<vector<int>> sect(n, {0});
vector<vector<pair<int, int>>> goL(n, {{-1, -1}}), goR(n, {{-1, -1}});
vector<tuple<int, int, int>> bridge;
for(int i = 0; i < m; i++) bridge.emplace_back(Y[i], L[i], R[i]);
sort(bridge.begin(), bridge.end());
vector<pair<int, int>> tower;
for(int i = 0; i < n; i++) tower.emplace_back(H[i], i);
sort(tower.begin(), tower.end());
set<int> active;
for(int i = 0; i < n; i++) active.insert(i);
int j = 0;
for(auto [y, l, r] : bridge){
while(j < n && tower[j].first < y) active.erase(tower[j++].second);
auto it = active.find(l);
int last = -1;
while(it != active.end() && *it <= r){
sect[*it].push_back(y);
goL[*it].push_back({-1, -1});
goR[*it].push_back({-1, -1});
if(last != -1) goR[last].back() = {*it, sz(sect[*it])-1}, goL[*it].back() = {last, sz(sect[last])-1};
last = *it;
it++;
}
}
map<pair<int, int>, ll> dist;
priority_queue<tuple<ll, int, int>> pq;
dist[make_pair(start, 0)] = 0;
pq.emplace(0, start, 0);
auto visit = [&](int x, int h, ll d){
auto p = make_pair(x, h);
if(!dist.count(p) || d < dist[p]){
dist[p] = d;
pq.emplace(-d, x, h);
}
};
while(!pq.empty()){
auto [d, x, h] = pq.top();
pq.pop();
d = -d;
if(d > dist[make_pair(x, h)]) continue;
if(goL[x][h].first != -1) visit(goL[x][h].first, goL[x][h].second, d+X[x]-X[goL[x][h].first]);
if(goR[x][h].first != -1) visit(goR[x][h].first, goR[x][h].second, d+X[goR[x][h].first]-X[x]);
if(h > 0) visit(x, h-1, d+sect[x][h]-sect[x][h-1]);
if(h < sz(sect[x])-1) visit(x, h+1, d+sect[x][h+1]-sect[x][h]);
}
if(!dist.count(make_pair(goal, 0))) return -1;
else return dist[make_pair(goal, 0)];
}
