#include <bits/stdc++.h>
#include "walk.h"
// #include "grader.cpp"
using namespace std;
#define inf (long long)(1e16)
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
vector<array<int,3>> lines;
for(int i = 0;i < x.size();i++){
lines.push_back({h[i],2,i});
}
for(int i = 0;i < l.size();i++){
lines.push_back({y[i],1,i});
}
vector<pair<int,int>> prev(x.size(),{-1,-1});
sort(lines.begin(),lines.end());
reverse(lines.begin(),lines.end());
set<int> alr;
int N = 0;
vector<vector<pair<int,int>>> edges(N);
for(auto [h,type,idx]:lines){// high->low, building->bridge
if(type == 2){
// buildings
alr.insert(idx);
continue;
}else{
auto it1 = alr.lower_bound(l[idx]);
auto it2 = alr.upper_bound(r[idx]);
int lid = -1,lidx = -1;
for(auto it = it1;it != it2;it++){
// add new points
// if(N >= 18) cout << "!!" << h << " " << type << " " << idx << endl;
int cid = N;
edges.push_back({});
N++;
auto [pid,ph] = prev[*it];
if(pid != -1){
edges[cid].push_back({pid,ph-h});
edges[pid].push_back({cid,ph-h});
}
prev[*it] = {cid,h};
if(lid != -1){
edges[cid].push_back({lid,x[*it]-x[lidx]});
edges[lid].push_back({cid,x[*it]-x[lidx]});
}
lid = cid,lidx = *it;
}
}
}
vector<int> floorId(x.size());
for(int i = 0;i < x.size();i++){
int cid = N;
edges.push_back({});
N++;
auto [pid,ph] = prev[i];
if(pid != -1){
edges[cid].push_back({pid,ph});
edges[pid].push_back({cid,ph});
}
floorId[i] = cid;
}
// do dijkstra
vector<long long> dist(N,inf);
dist[floorId[s]] = 0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;// dist,idx
pq.push({0,floorId[s]});
while(!pq.empty()){
auto [cdist,cur] = pq.top();
pq.pop();
if(dist[cur] != cdist) continue;
for(auto [nxt,w]:edges[cur]){
if(dist[cur]+w < dist[nxt]){
dist[nxt] = dist[cur]+w;
pq.push({dist[nxt],nxt});
}
}
}
// for(int i = 0;i < N;i++){
// cout << i << ":";
// for(auto [nxt,w]:edges[i]){
// cout << "(" << nxt << "," << w << ") ";
// }
// cout << endl;
// }
// for(auto &i:floorId) cout << i << " ";cout << endl;
// for(auto &i:dist) {
// if(i == inf) cout << "-1 ";
// else cout << i << " ";
// }
// cout << endl;
if(dist[floorId[g]] == inf){
return -1;
}else{
return dist[floorId[g]];
}
}
