#include "walk.h"
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#define int long long
using namespace std;
struct graph
{
int n = 0;
vector<vector<pair<int,int>>> adjlist;
vector<int> coord_x;
int add_vertex(int x)
{
n++;
adjlist.push_back(vector<pair<int,int>>());
coord_x.push_back(x);
return n - 1;
}
void add_edge(int from, int to, int w)
{
adjlist[from].push_back({to, w});
adjlist[to].push_back({from, w});
}
int dijkstra(int s, int z)
{
vector<int> dists(n, -1);
dists[s] = 0;
priority_queue<pair<int,int>> pq;
pq.push({0, s});
while (!pq.empty())
{
int curr = pq.top().second;
pq.pop();
for (auto p : adjlist[curr])
{
int next = p.first;
int t = p.second + dists[curr];
if (dists[next] != -1 && t >= dists[next]) continue;
dists[next] = t;
pq.push({-t, next});
}
}
return dists[z];
}
};
struct graph_creator
{
int n;
set<int> active;
map<int,int> last_vertices;
vector<signed> heights;
vector<signed> hpos;
vector<set<int>> walk_start;
vector<set<int>> walk_end;
int sx, zx;
int sv, zv;
graph g;
int _addv(int x, int y)
{
int nv = g.add_vertex(x);
if (active.find(y) != active.end())
{
g.add_edge(nv, last_vertices[y], hpos[x] - hpos[g.coord_x[last_vertices[y]]]);
}
active.insert(y);
last_vertices[y] = nv;
return nv;
}
int create_vert(int x, int y)
{
int nv = _addv(x, y);
set<int>::iterator cur = active.find(y);
auto nx = cur;
nx++;
if (nx != active.end() && (*nx) <= heights[x])
{
int nh = (*nx);
int hnv = _addv(x, nh);
g.add_edge(hnv, nv, nh - y);
}
if (cur != active.begin())
{
auto prev = cur;
prev--;
int lh = (*prev);
int lnv = _addv(x, lh);
g.add_edge(nv, lnv, y - lh);
}
return nv;
}
void create()
{
for (int i = 0; i < n; i++)
{
for (auto h : walk_start[i])
{
create_vert(i, h);
}
if (i == sx)
{
sv = create_vert(i, 0);
}
else if (i == zx)
{
zv = create_vert(i, 0);
}
for (auto h : active)
{
if (h > heights[i]) break;
create_vert(i, h);
}
for (auto h : walk_end[i])
{
active.erase(h);
}
active.erase(0);
}
}
};
int min_distance(vector<signed> x, vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g)
{
graph_creator gc;
gc.heights = h;
gc.n = x.size();
gc.hpos = x;
gc.walk_start.resize(gc.n);
gc.walk_end.resize(gc.n);
gc.sx = s;
gc.zx = g;
int k = l.size();
for (int i = 0; i < k; i++)
{
gc.walk_start[l[i]].insert(y[i]);
}
for (int i = 0; i < k; i++)
{
if (gc.walk_start[r[i]].find(y[i]) == gc.walk_start[r[i]].end())
{
gc.walk_end[r[i]].insert(y[i]);
}
else
{
gc.walk_start[r[i]].erase(y[i]);
}
}
gc.create();
return gc.g.dijkstra(gc.sv, gc.zv);
}
