#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 = {inf};
vector<int> X = {-1};
vector<int> Y = {-1};
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-1;
}
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, int &ptp){
if(y > past){
int pt = addnode(x,y);
if(mep[y] != 0){
addedge(mep[y],pt);
}
mep[y] = pt;
past = y;
if(ptp != -1){
addedge(ptp,pt);
}
ptp = pt;
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();
X.clear();
Y.clear();
sat.clear();
mep.clear();
addnode(-1,-1);
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());
pont[i].resize(unique(pont[i].begin(), pont[i].end() ) - pont[i].begin());
while(!pont[i].empty() && pont[i].back() > h[i]) pont[i].pop_back();
if(i == s || i == g){
int past = -1;
int ptp = -1;
if(i == s) si = addfull(x[i],0,past,ptp);
else if(i == g) gi = addfull(x[i],0,past,ptp);
mep[0] = 0;
for(int j : sat){
if(j > h[i]) break;
addfull(x[i],j,past,ptp);
}
}
else{
int past = -1;
int ptp = -1;
for(int j : pont[i]){
auto it = sat.find(j);
if(it != sat.begin()){
advance(it,-1);
addfull(x[i],*it,past,ptp);
advance(it,1);
}
addfull(x[i],*it,past,ptp);
advance(it,1);
if(it != sat.end()){
if(*it <= h[i]) addfull(x[i],*it,past,ptp);
}
}
}
for(int j : rmv[i]){
sat.erase(sat.find(y[j]));
if(sat.find(y[j]) == sat.end()) mep[y[j]] = 0;
}
}
sssp(si);
if(d[gi] == inf) return -1;
return d[gi];
}
