#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<cstring>
#include<set>
#include<queue>
#include "walk.h"
using namespace std;
const int MAX_N=3e6+5;
int N;
int szx;
int szpoints;
map<pair<int,int>,int>pospoint;
map<int,int>posx;
set<int>pointsx[MAX_N];
int right[MAX_N];
int up[MAX_N];
void add_point(int x,int y)
{
if(pospoint.find({x,y})==pospoint.end())
{
pospoint[{x,y}]=szpoints++;
}
pointsx[posx[x]].insert(y);
}
vector<pair<int,long long>>g[MAX_N];
long long dist[MAX_N];
void add_edge(int u,int v,int cost)
{
g[u].push_back({v,cost});
g[v].push_back({u,cost});
}
long long dijkstra(int s,int t)
{
priority_queue<pair<long long,int>>q;
q.push({0,s});
memset(dist,-1,sizeof(dist));
dist[s]=0;
while(q.size())
{
long long d=-q.top().first;
int u=q.top().second;
q.pop();
if(d>dist[u])continue;
for(auto [v,edge]:g[u])
{
if(dist[u]+edge<dist[v] or dist[v]==-1)
{
dist[v]=dist[u]+edge;
q.push({-dist[v],v});
}
}
}
return dist[t];
}
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)
{
N=x.size();
if(N==1)return 0;
for(int i=0;i<x.size();i++)
{
if(posx.find(x[i])==posx.end())
{
posx[x[i]]=szx++;
}
}
for(int i=0;i<x.size();i++)
{
add_point(x[i],0);
add_point(x[i],h[i]);
add_edge(szpoints-1,szpoints-2,h[i]);
}
vector<pair<int,int>>order;
for(int i=0;i<y.size();i++)
{
order.push_back({y[i],i});
}
sort(order.begin(),order.end());
for(int id=0;id<l.size();id++)
{
int i=order[id].second;
int prevx=-1,prevy;
for(int j=l[i];j<=r[i];j++)
{
if(h[j]>=y[i])
{
add_point(x[j],y[i]);
}
else continue;
if(prevx!=-1)
{
add_edge(pospoint[{prevx,prevy}],pospoint[{x[j],y[i]}],x[j]-prevx);
}
auto it=pointsx[posx[x[j]]].lower_bound(y[i]);
it--;
int yy=((*it));
add_edge(pospoint[{x[j],yy}],pospoint[{x[j],y[i]}],y[i]-yy);
prevx=x[j];
prevy=y[i];
}
}
return dijkstra(pospoint[{x[s],0}],pospoint[{x[g],0}]);
}
