#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
map< pair<int,int>, vector< pair<int,int> > >edges;
map< pair<int,int>,long long> mem;
set<int> seen[nmax];
priority_queue< pair<long long,pair<int,int> > > pq;
vector<int> mem_x,mem_h;
int dist(pair<int,int> a,pair<int,int> b)
{
return abs(mem_x[a.first]-mem_x[b.first])+abs(a.second-b.second);
}
void dij(pair<int,int> start)
{
pq.push({0,start});
while(pq.size())
{
pair<long long,pair<int,int> > tp=pq.top();
pq.pop();
if(mem.count(tp.second))continue;
tp.first=-tp.first;
mem[tp.second]=tp.first;
//cout<<tp.first<<" "<<tp.second.first<<" "<<tp.second.second<<endl;
for(auto k:edges[tp.second])
pq.push({-(dist(k,tp.second)+tp.first),k});
}
}
vector< pair<int,int> > tree[4*nmax];
void build(int node,int l,int r)
{
if(l==r)
{
tree[node].push_back({mem_h[l],l});
return;
}
int av=(l+r)/2;
build(node*2,l,av);
build(node*2+1,av+1,r);
tree[node]=tree[node*2];
for(auto k:tree[node*2+1])
tree[node].push_back(k);
sort(tree[node].begin(),tree[node].end());
}
vector<int> given;
void query(int node,int l,int r,int lq,int rq,int low)
{
if(l==lq&&r==rq)
{
int pointer=tree[node].size()-1;
while(pointer>=0&&tree[node][pointer].first>=low)
{
given.push_back(tree[node][pointer].second);
pointer--;
}
return;
}
int av=(l+r)/2;
if(lq<=av)query(node*2,l,av,lq,min(av,rq),low);
if(av<rq)query(node*2+1,av+1,r,max(av+1,lq),rq,low);
}
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)
{
mem_x=x;
mem_h=h;
build(1,0,x.size()-1);
for(int t=0;t<l.size();t++)
{
int prv=-1;
given={};
query(1,0,x.size()-1,l[t],r[t],y[t]);
sort(given.begin(),given.end());
for(auto j:given)
if(h[j]>=y[t])
{
seen[j].insert(y[t]);
if(prv!=-1)
{
edges[{j,y[t]}].push_back({prv,y[t]});
edges[{prv,y[t]}].push_back({j,y[t]});
}
prv=j;
}
}
seen[s].insert(0);
seen[g].insert(0);
for(int i=0;i<x.size();i++)
{
int prv=-1;
for(auto k:seen[i])
{
if(prv!=-1)
{
edges[{i,prv}].push_back({i,k});
edges[{i,k}].push_back({i,prv});
}
prv=k;
}
}
dij({s,0});
if(mem.count({g,0}))return mem[{g,0}];
return -1;
}
