#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pair;
const int Nmax = 2e6 + 5;
///13:05
vector<int> x, h, l, r, y;
vector<int> newl, newr, newy;
vector<Pair> v[Nmax];
int nr;
void add_new(int l, int r, int y)
{
if(l == r) return;
newl.push_back(l); newr.push_back(r); newy.push_back(y);
}
auto cmp_buildings = [](int i, int j)
{
return h[i] > h[j];
};
auto cmp_skywalks = [] (int i, int j)
{
return y[i] > y[j];
};
void add_edge(int x, int y, int cost)
{
v[x].push_back({y, cost});
v[y].push_back({x, cost});
}
void adjust(int node)
{
newl.clear(); newr.clear(); newy.clear();
int m = l.size();
vector<int> s, pref, suff;
s.resize(m);
pref.resize(node+1);
suff.resize(h.size()-node);
iota(s.begin(), s.end(), 0);
iota(pref.begin(), pref.end(), 0);
iota(suff.begin(), suff.end(), node);
sort(s.begin(), s.end(), cmp_skywalks);
sort(pref.begin(), pref.end(), cmp_buildings);
sort(suff.begin(), suff.end(), cmp_buildings);
int id1 = 0, id2 = 0, mx = -1, mn = h.size();
for(auto it : s)
{
while(id1 < pref.size() && h[pref[id1]] >= y[it])
mx = max(mx, pref[id1]), id1++;
while(id2 < suff.size() && h[suff[id2]] >= y[it])
mn = min(mn, suff[id2]), id2++;
if(l[it] < node && node < r[it])
{
add_new(l[it], mx, y[it]);
add_new(mx, mn, y[it]);
add_new(mn, r[it], y[it]);
}
else add_new(l[it], r[it], y[it]);
}
swap(l, newl); swap(r, newr); swap(y, newy);
}
#define left_son ((node<<1))
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
class SegTree
{
int lazy[Nmax<<2];
public:
void propag(int node)
{
if(!lazy[node]) return;
lazy[left_son] = lazy[right_son] = lazy[node];
lazy[node] = 0;
}
void init()
{
lazy[1] = -1;
}
void update(int node, int st, int dr, int L, int R, int V)
{
if(L <= st && dr <= R)
{
lazy[node] = V;
return;
}
propag(node);
if(L <= mid) update(left_son, st, mid, L, R, V);
if(mid < R) update(right_son, mid+1, dr, L, R, V);
}
int query(int node, int st, int dr, int pos)
{
if(st == dr)
return lazy[node];
propag(node);
if(pos <= mid) return query(left_son, st, mid, pos);
else return query(right_son, mid+1, dr, pos);
}
} aint;
void add_point(int l, int r, int id)
{
aint.update(1, 0, h.size()-1, l, r, id);
}
int find_point(int x)
{
return aint.query(1, 0, h.size()-1, x);
}
void find_graph(int Start, int Finish)
{
int m = y.size(), n = h.size();
vector<int> s(m);
iota(s.begin(), s.end(), 0);
sort(s.begin(), s.end(), cmp_skywalks);
reverse(s.begin(), s.end());
vector<Pair> points;
aint.init();
points.push_back({Start, m});
points.push_back({Finish, m+1});
y.push_back(0);
y.push_back(0);
add_point(Start, Start, m);
add_point(Finish, Finish, m+1);
m+=2;
for(auto it : s)
{
points.push_back({ l[it], it });
points.push_back({ r[it], it });
int p1, p2;
p1 = find_point(l[it]);
p2 = find_point(r[it]);
if(p1 != -1)
points.push_back({ l[it], p1 });
if(p2 != -1)
points.push_back({ r[it], p2 });
add_point(l[it], r[it], it);
}
vector<vector<Pair>> vx(n), vy(m);
nr = 0;
for(auto p : points)
{
++nr;
vx[p.first].push_back({y[p.second], nr});
vy[p.second].push_back({x[p.first], nr});
}
int i, j;
for(i=0; i<n; ++i)
{
sort(vx[i].begin(), vx[i].end());
for(j=0; j+1<vx[i].size(); ++j)
add_edge(vx[i][j].second, vx[i][j+1].second, vx[i][j+1].first - vx[i][j].first);
}
for(i=0; i<m; ++i)
{
sort(vy[i].begin(), vy[i].end());
for(j=0; j+1<vy[i].size(); ++j)
add_edge(vy[i][j].second, vy[i][j+1].second, vy[i][j+1].first - vy[i][j].first);
}
}
ll dijkstra(int S, int F)
{
priority_queue< pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>> > heap;
vector<ll> d(nr+1, LLONG_MAX);
d[S] = 0;
heap.push({0, S});
while(heap.size())
{
int node; ll dist;
tie(dist, node) = heap.top();
heap.pop();
if(dist != d[node]) continue;
if(node == F) return d[F];
for(auto it : v[node])
if(d[it.first] > d[node] + it.second)
{
d[it.first] = d[node] + it.second;
heap.push({d[it.first], it.first});
}
}
return -1;
}
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int Start, int Finish)
{
x = X; h = H; l = L; r = R; y = Y;
adjust(Start);
adjust(Finish);
find_graph(Start, Finish);
return dijkstra(1, 2);
}
