#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
const long long inf = 1e18;
int cont = 1;
vector<vector<pair<int,int>>> adjlst;
vector<long long int> d;
vector<int> X;
vector<int> Y;
multiset<int> sat;
map<int,int> mep;
int addnode(int x, int y){
X.push_back(x);
Y.push_back(y);
adjlst.push_back({});
d.push_back(inf);
cont++;
return cont;
}
void addedge(int u, int v){
int w = abs(X[u] - X[v]) + abs(Y[u] - Y[v]);
adjlst[u].push_back({v,w});
adjlst[v].push_back({u,w});
}
int addfull(int x, int y, int &past){
if(y > past){
int pt = addnode(x,y);
if(mep[y] != 0){
addedge(mep[y],pt);
}
mep[y] = pt;
past = y;
return pt;
}
return -1;
}
void sssp(int s){
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
pq.push({0,s});
while(!pq.empty()){
pair<long long, int> ii = pq.top();
pq.pop();
int i = ii.second;
if(ii.first < d[i]){
d[i] = ii.first;
for(pair<int,int> ii : adjlst[i]){
if(ii.second + d[i] < d[ii.first]) pq.push({ii.second + d[i], ii.first});
}
}
}
}
}
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 = x.size();
int M = l.size();
cont = 0;
adjlst.clear();
d.clear();
sat.clear();
mep.clear();
vector<int> line[N + 5];
vector<int> add[N + 5];
vector<int> rmv[N + 5];
vector<int> pont[N + 5];
int itl = s;
int itr = s;
vector<pair<int,int>> johns;
vector<pair<int,int>> johng;
for(int i = 0; i < M; i++){
if(l[i] < s && s < r[i]) johns.push_back({y[i],i});
if(l[i] < g && g < r[i]) johng.push_back({y[i],i});
}
sort(johns.begin(),johns.end());
sort(johng.begin(),johng.end());
for(int i = 0; i < johns.size(); i++){
if(johns[i].first <= h[s]) continue;
int yp = y[johns[i].second];
while(h[itl] < yp) itl--;
while(h[itr] < yp) itr++;
pont[itl].push_back(yp);
pont[itr].push_back(yp);
}
itl = g;
itr = g;
for(int i = 0; i < johng.size(); i++){
if(johng[i].first <= h[g]) continue;
int yp = y[johng[i].second];
while(h[itl] < yp) itl--;
while(h[itr] < yp) itr++;
pont[itl].push_back(yp);
pont[itr].push_back(yp);
}
for(int i = 0; i < M; i++){
pont[l[i]].push_back(y[i]);
pont[r[i]].push_back(y[i]);
}
for(int i = 0; i < M; i++){
add[l[i]].push_back(i);
rmv[r[i]].push_back(i);
}
int si,gi;
for(int i = 0; i < N; i++){
for(int j : add[i]){
sat.insert(y[j]);
}
sort(pont[i].begin(),pont[i].end());
if(i == s || i == g){
int past = -1;
if(i == s) si = addfull(x[i],0,past);
else if(i == g) gi = addfull(x[i],0,past);
for(int j : sat){
addfull(x[i],j,past);
}
}
else{
int past = -1;
for(int j : pont[i]){
auto it = sat.find(j);
if(it != sat.begin()){
advance(it,-1);
addfull(x[i],*it,past);
advance(it,1);
}
addfull(x[i],*it,past);
advance(it,1);
if(it != sat.end()){
addfull(x[i],*it,past);
}
}
}
}
sssp(si);
if(d[gi] == inf) return -1;
return d[gi];
}
