#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 2000005;
const int N = 100005;
const ll INF = 2000000000000000000LL;
vector<array<int, 2>> adj[M];
vector<array<int, 2>> isAt[N];
int cnode = 0;
///usr/include/c++/10/bits/stl_heap.h|209|error: ‘bool Comparator::operator()(const std::__debug::array<long long int, 2>&, const std::__debug::array<long long int, 2>&) const’ is private within this context|
struct Comparator
{
bool operator() (const array<ll, 2>& ar1, const array<ll, 2>& ar2) const
{
return tie(ar1[1], ar1[0]) < tie(ar2[1], ar2[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) {
int snode = -1;
int gnode = -1;
for (int i = 0; i < x.size(); i++)
{
isAt[i].push_back({cnode, 0});
if (i == s)
{
snode = cnode;
}
if (i == g)
{
gnode = cnode;
}
cnode++;
}
vector<array<int, 2>> byHeight;
for (int i = 0; i < l.size(); i++)
{
byHeight.push_back({y[i], i});
}
sort(byHeight.begin(), byHeight.end());
set<int> ok;
for (int i = 0; i < x.size(); i++) ok.insert(i);
for (int ci = 0; ci < l.size(); ci++)
{
int i = byHeight[ci][1];
int prev = -1;
for (auto it = ok.lower_bound(l[i]); it != ok.end() && *it <= r[i]; )
{
int j = *it;
if (h[j] >= y[i])
{
adj[cnode].push_back({isAt[j].back()[0], abs(isAt[j].back()[1] - y[i])});
adj[isAt[j].back()[0]].push_back({cnode, abs(isAt[j].back()[1] - y[i])});
isAt[j].push_back({cnode, y[i]});
if (prev != -1)
{
adj[cnode].push_back({cnode - 1, x[j] - x[prev]});
adj[cnode - 1].push_back({cnode, x[j] - x[prev]});
}
prev = j;
cnode++;
it++;
} else
{
it = ok.erase(it);
}
}
}
set<array<ll, 2>, Comparator> sett;
sett.insert({snode, 0});
vector<ll> dist(M, INF);
dist[snode] = 0;
while (!sett.empty())
{
auto cur = *sett.begin();
sett.erase(sett.begin());
for (auto next : adj[cur[0]])
{
if (cur[1] + next[1] < dist[next[0]])
{
if (dist[next[0]] != INF)
{
sett.erase({next[0], dist[next[0]]});
}
dist[next[0]] = cur[1] + next[1];
sett.insert({next[0], cur[1] + next[1]});
}
}
}
if (dist[gnode] == INF) return -1;
return dist[gnode];
}
