#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> ppll;
ll dijkstra(map<pll, vector<ppll>> g, ll s, ll e){
map<pll, ll> dist, vis;
priority_queue<ppll, vector<ppll>, greater<ppll>> pq; pq.push({0, {s, 0}});
while(pq.size()){
auto[d, node] = pq.top(); pq.pop();
if(vis[node]) continue;
vis[node] = 1;
dist[node] = d;
for(auto[x_dist, x]: g[node]) pq.push({d+x_dist, x});
}
return (dist[{e, 0}] ? dist[{e, 0}] : -1);
}
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) {
ll n = X.size(), m = L.size(), s = S, e = G;
vector<ll> x(n), h(n), l(m), r(m), y(m);
for(ll i = 0; i < n; i++) x[i] = X[i], h[i] = H[i];
for(ll i = 0; i < m; i++) l[i] = L[i], r[i] = R[i], y[i] = Y[i];
vector<vector<ll>> v(n);
map<pll, vector<ppll>> g;
for(ll i = 0; i < m; i++){
for(ll j = l[i]; j <= r[i]; j++) if(h[j] >= y[i]) {
v[j].push_back(y[i]);
if(j > l[i] && h[j-1] >= y[i]) {
g[{x[j], y[i]}].push_back({x[j] - x[j-1], {x[j-1], y[i]}});
g[{x[j-1], y[i]}].push_back({x[j] - x[j-1], {x[j], y[i]}});
}
}
}
for(ll i = 0; i < n; i++) sort(v[i].begin(), v[i].end());
for(ll i = 0; i < n; i++) if(v[i].size()) {
g[{x[i], 0}].push_back({v[i][0], {x[i], v[i][0]}});
g[{x[i], v[i][0]}].push_back({v[i][0], {x[i], 0}});
for(ll j = 1; j < v[i].size(); j++){
g[{x[i], v[i][j-1]}].push_back({v[i][j] - v[i][j-1], {x[i], v[i][j]}});
g[{x[i], v[i][j]}].push_back({v[i][j] - v[i][j-1], {x[i], v[i][j-1]}});
}
}
return dijkstra(g, x[s], x[e]);
}
