#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
const long long inf=1e18;
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);
}
int stop=0;
void dij(pair<int,int> start)
{
pq.push({0,start});
while(pq.size()&&mem.count({stop,0})==0)
{
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);
}
vector< int/*h*/> to_push[nmax],to_pop[nmax];
set< pair<int/*h*/,long long/*value*/> > active;
map<int,int> cnt;
long long special(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g)
{
for(int i=0;i<l.size();i++)
{
to_push[l[i]].push_back(y[i]);
to_pop[r[i]].push_back(y[i]);
}
for(int i=0;i<x.size();i++)
{
sort(to_push[i].begin(),to_push[i].end());
sort(to_pop[i].begin(),to_pop[i].end());
}
active.insert({0,0});
cnt[0]++;
long long mini=1e18;
for(int i=0;i<x.size();i++)
{
for(auto k:to_push[i])
{
cnt[k]++;
long long mini=inf;
set< pair<int/*h*/,long long/*value*/> >::iterator it=active.lower_bound({k,0});
if(it!=active.end())
{
if((*it).first==k)continue;
}
if(it!=active.end())
{
mini=min(mini,(*it).second+abs(k-(*it).first));
}
if(it!=active.begin())
{
it--;
mini=min(mini,(*it).second+abs(k-(*it).first));
}
active.insert({k,mini});
}
for(auto k:to_pop[i])
{
cnt[k]--;
if(cnt[k])continue;
set< pair<int/*h*/,long long/*value*/> >::iterator it=active.lower_bound({k,0});
if(i==x.size()-1)
{
mini=min(mini,(*it).first+(*it).second);
}
active.erase(*it);
}
if(i==0)
{
active.erase({0,0});
cnt[0]--;
}
if(i!=x.size()-1&&active.size()==0)return -1;
/*
cout<<i<<" -> "<<endl;
for(auto k:active)
cout<<k.first<<" "<<k.second<<endl;
cout<<"---"<<endl;
*/
}
for(auto k:active)
mini=min(mini,k.first+k.second);
mini=mini+x[x.size()-1]-x[0];
return mini;
}
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)
{
if(s==0&&g==x.size()-1)return special(x,h,l,r,y,s,g);
stop=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;
}
