#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define mk make_pair
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pb push_back
#define debug printf
#define pii pair<int,int>
#define sz(x) (int)( x.size() )
const int MAX = 1e7+10 ;
const ll inf = 1e18+10 ;
using namespace std ;
struct Event
{
int type , h , id ;
Event(int type = 0 ,int h = 0 ,int id = 0 ) : type(type) , h(h) , id(id) {}
bool operator < ( Event other ) const
{
if(h == other.h) return type < other.type ;
return h > other.h ;
}
} ;
int N , M ;
vector<pii> numX[MAX] ;
vector<Event> sweep ;
map< pii , int > mp ;
set<int> s ;
vector<pii> adj[MAX] ;
ll dist[MAX] ;
void dijkstra(int S)
{
lp(i,1,sz(mp)+1) dist[i] = inf ;
dist[ S ] = 0 ;
priority_queue< pair<ll,int> , vector< pair<ll,int> > , greater< pair<ll,int> > > fila ;
fila.push( mk(0,S) ) ;
while(!fila.empty())
{
int x = fila.top().ss ;
ll d = fila.top().ff ;
fila.pop() ;
if(d != dist[x]) continue ;
for(auto e : adj[x] )
{
ll dd = d + (ll)e.ss ;
if( dd >= dist[e.ff] ) continue ;
dist[e.ff] = dd;
fila.push(mk(dd, e.ff) ) ;
}
}
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int S, int G)
{
N = sz(h) ;
M = sz(l) ;
lp(i,0,N)
{
mp.insert( mk( mk(i , 0) , sz(mp) + 1) ) ;
sweep.pb( Event(0 , h[i] , i) ) ;
}
lp(i,0,M) sweep.pb( Event(1, y[i] , i ) ) ;
sort(all(sweep)) ;
for(auto e : sweep )
{
if(e.type == 0)
{
s.insert(e.id) ;
continue ;
}
auto L = s.find( l[e.id] ) ;
auto R = s.find( r[e.id] ) ;
vector<int> aux ;
while( true )
{
if( mp.find( mk( *L , e.h ) ) == mp.end() )
mp.insert( mk(mk(*L , e.h) , sz(mp) + 1) ) ;
aux.pb( *L ) ;
if(L == R) break ;
L++ ;
}
for(int i = 0 ; i < sz(aux) - 1 ; i++ )
{
int id1 = aux[i] ;
int id2 = aux[i+1] ;
int a1 = mp[mk(id1, e.h) ] ;
int a2 = mp[mk(id2, e.h) ] ;
adj[a1].pb( mk( a2, x[id2] - x[id1] ) ) ;
adj[ a2 ].pb( mk( a1, x[id2] - x[id1] ) ) ;
}
}
for(auto e : mp ) numX[ e.ff.ff ].pb( mk( e.ff.ss, e.ss ) ) ;
lp(i,0,N)
for(int j = 1 ; j < sz(numX[i]) ; j++ )
{
int dist = numX[i][j].ff - numX[i][j-1].ff ;
adj[ numX[i][j-1].ss ].pb(mk( numX[i][j].ss , dist ) );
adj[ numX[i][j].ss ].pb(mk( numX[i][j-1].ss , dist ) );
}
S = mp[ mk(S,0) ] ;
G = mp[ mk(G,0) ] ;
dijkstra(S) ;
return dist[ G ] == inf ? -1 : dist[G] ;
}
