#include "walk.h"
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct node{
long long int dis,id;
}t[1000005];
long long int p[1000005],hp[1000005],dis[1000005],m,n,road[1000005],map[1000005][3],pointer[100005][50][2],num[100005],cont,st,cnt;
int connect(int a,int b,int len)
{
//cout<<a<<" "<<p[a]<<" "<<hp[a]<<" "<<b<<" "<<p[b]<<" "<<hp[b]<<endl;
cont++;
map[cont][0]=b;
map[cont][1]=road[a];
map[cont][2]=len;
road[a]=cont;
cont++;
map[cont][0]=a;
map[cont][1]=road[b];
map[cont][2]=len;
road[b]=cont;
return 0;
}
struct cmp{
bool operator()(const node &a,const node &b)
{
return a.dis>b.dis;
}
};
int dijk()
{
for(int i=1;i<=cnt;i++)dis[i]=1000000000000;
dis[st]=0;
t[1].id=st;
t[1].dis=0;
long long int pp=1;
while(pp>=1)
{
pop_heap(t+1,t+pp+1,cmp());
long long int x=t[pp].id,len=t[pp].dis;
pp--;
if(len!=dis[x])
{
continue;
}
//cout<<x<<" "<<len<<" "<<p[x]<<endl;
long long int g=road[x];
while(g!=-1){
long long int now=map[g][0];
//cout<<now<<" "<<dis[now]<<" "<<p[now]<<" "<<hp[now]<<endl;
if(len+map[g][2]<dis[now]){
dis[now]=len+map[g][2];
pp++;
t[pp].id=now;
t[pp].dis=dis[now];
push_heap(t+1,t+pp+1,cmp());
}
g=map[g][1];
}
for(int i=1;i<=num[p[x]];i++)
{
long long int now=pointer[p[x]][i][0];
if(now==x)continue;
//cout<<now<<" "<<dis[now]<<" "<<p[now]<<" "<<hp[now]<<endl;
if(len+abs(hp[x]-pointer[p[x]][i][1])<dis[now]){
dis[now]=len+abs(hp[x]-pointer[p[x]][i][1]);
pp++;
t[pp].id=now;
t[pp].dis=dis[now];
push_heap(t+1,t+pp+1,cmp());
}
g=map[g][1];
}
//cout<<endl;
}
return 0;
}
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();
m=l.size();
for(int i=0;i<=n*m;i++)road[i]=-1;
st=0;
for(int i=0;i<m;i++){
cnt++;
num[l[i]]++;
p[cnt]=l[i];
hp[cnt]=y[i];
pointer[l[i]][num[l[i]]][0]=cnt;
pointer[l[i]][num[l[i]]][1]=y[i];
long long int pr=cnt,prex=x[l[i]];
for(int j=l[i]+1;j<=r[i];j++){
if(h[j]>=y[i])
{
cnt++;
num[j]++;
p[cnt]=j;
hp[cnt]=y[i];
pointer[j][num[j]][0]=cnt;
pointer[j][num[j]][1]=y[i];
connect(cnt,pr,x[j]-prex);
pr=cnt;
prex=x[j];
}
}
}
num[s]++;
cnt++;
p[cnt]=s;
pointer[s][num[s]][0]=cnt;
st=cnt;
num[g]++;
cnt++;
p[cnt]=g;
pointer[g][num[g]][0]=cnt;
dijk();
return dis[cnt];
}
