#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Seg {
int n;
vector<int> t;
Seg(int sz) {
n = sz;
t = vector<int>(2*n);
}
void update(int p, int v) {
for (t[p += n] = v; p > 1; p /= 2) t[p/2] = max(t[p], t[p^1]);
}
int query(int l, int r) {
int ret = 0;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1) ret = max(ret, t[l++]);
if (r&1) ret = max(ret, t[--r]);
}
return ret;
}
int upper_bound(int l, int v) {
int lo = l+1, hi = n-1;
int bnd = l;
while (lo <= hi) {
int m = (lo+hi)/2;
int q = query(l+1, m+1);
if (q < v) bnd = m, lo = m+1;
else hi = m-1;
}
return bnd+1;
}
};
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
int n = (int)x.size();
int m = (int)y.size();
map<pair<int, int>, vector<pair<pair<int, int>, int>>> mp;
vector<set<int>> pts(n, {0});
Seg seg(n);
for (int i = 0; i < n; i++) seg.update(i, h[i]);
for (int i = 0; i < m; i++) {
int j = l[i];
while (1) {
int j2 = seg.upper_bound(j, y[i]);
if (j2 > r[i]) break;
//cout << i << " -> " << j << " " << j2 << endl;
mp[pair<int, int>{j, y[i]}].push_back({pair<int, int>{j2, y[i]}, x[j2]-x[j]});
mp[pair<int, int>{j2, y[i]}].push_back({pair<int, int>{j, y[i]}, x[j2]-x[j]});
pts[j].insert(y[i]);
pts[j2].insert(y[i]);
j = j2;
}
}
map<pair<int, int>, ll> dist;
for (int i = 0; i < n; i++) {
int pr = -1;
for (int y : pts[i]) {
if (pr != -1) {
mp[pair<int, int>{i, y}].push_back({pair<int, int>{i, pr}, y-pr});
mp[pair<int, int>{i, pr}].push_back({pair<int, int>{i, y}, y-pr});
}
pr = y;
dist[pair<int, int>{i, y}] = 1e18;
}
}
priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
pq.push({0ll, {s, 0}});
dist[{s, 0}] = 0ll;
//cout << "Adj: " << endl;;
//for (auto [pt, v] : mp) for (auto pt2d:v) {
// cout << pt.first << " " << pt.second << ": " << pt2d.first.first << " " << pt2d.first.second << " w:" << pt2d.second << endl;
//}
while (pq.size()) {
auto [d, pt] = pq.top(); pq.pop();
if (d != dist[pt]) continue;
for (auto [npt, w] : mp[pt]) if (dist[npt] > d+w) {
dist[npt] = d+w;
pq.push({d+w, npt});
}
if (dist[{g, 0}] != 1e18) {
//cout << endl << "Dist: " << endl;
//for (auto [pt, d] : dist) {
// cout << pt.first << " " << pt.second << ": " << d << endl;
//}
return dist[{g, 0}];
}
}
return -1;
}
