#include "walk.h"
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<ll, int>;
#define sz(x) (int)x.size()
#define fi first
#define se second
const int MAXN = 3e6;
const ll INF = 1e18;
int n;
vi G[MAXN]; vll W[MAXN];
void create_link(int u, int v, ll w) {
G[u].push_back(v);
G[v].push_back(u);
W[u].push_back(w);
W[v].push_back(w);
}
ll dijkstra(int s, int g) {
vll dist(n, INF);
priority_queue<ii> q;
dist[s] = 0;
q.push( {-0, s} );
while(!q.empty()) {
ii p = q.top(); q.pop();
int u = p.se;
if(dist[u] != -p.fi) continue;
for(int i=0; i<sz(G[p.se]); i++) {
int v = G[p.se][i];
ll w = W[p.se][i];
if(-p.fi + w < dist[v]) {
dist[v] = -p.fi + w;
q.push( { -dist[v], v } );
}
}
}
if(dist[g] == INF) return -1;
return dist[g];
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
n = sz(x);
vector<pair<int, int>> bridge, re;
for(int i=0; i<sz(l); i++) bridge.push_back( { y[i], i } );
sort(bridge.begin(), bridge.end());
for(int i=0; i<n; i++) re.push_back( { 0, i } );
for(pair<int,int> p : bridge) {
int index = p.se;
create_link(re[l[index]].se, n, p.fi - re[l[index]].fi);
re[l[index]] = { p.fi, n };
pair<int,int> current_node = { x[l[index]], n };
n++;
for(int i = l[index]+1; i <= r[index]; i++) {
if(p.fi <= h[i]) {
create_link(current_node.se, n, x[i] - current_node.fi);
current_node = { x[i], n };
n++;
create_link(current_node.se, re[i].se, p.fi - re[i].fi);
re[i] = { p.fi, current_node.se };
}
}
}
return dijkstra(s, g);
}
