#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 2000013
#define INF 1000000007
#define LLINF 2696969696969696969
#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, M, S, T, V;
pll arr[MAXN];
vpl edge[MAXN];
vpl edge1[MAXN];
vl hs[MAXN];
vector<array<ll, 3> > events;
set<int> s;
int st[MAXN];
ll dist[MAXN];
ll ans;
ll dijkstra()
{
S = st[S]; T = st[T];
priority_queue<pll, vector<pll>, greater<pll> > q;
FOR(i, 0, V) dist[i] = LLINF;
// FOR(i, 0, V)
// {
// for (auto e : edge1[i])
// {
// cerr << i << " -> " << e.se << " len " << e.fi << endl;
// }
// }
dist[S] = 0; q.push({0, S});
while(!q.empty())
{
ll d = q.top().fi; int u = q.top().se; q.pop();
if (u == T) break;
if (d != dist[u]) continue;
for (auto e : edge1[u])
{
ll nd = d + e.fi; int v = e.se;
if (dist[v] > nd)
{
dist[v] = nd;
q.push({nd, v});
}
}
}
return dist[T];
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int source, int sink)
{
N = SZ(x);
FOR(i, 0, N)
{
arr[i] = {x[i], h[i]};
}
M = SZ(y);
FOR(i, 0, M)
{
int u = l[i], v = r[i], h = y[i];
edge[u].PB({h, v});
edge[v].PB({h, u});
}
S = source; T = sink;
FOR(i, 0, N)
{
events.PB({arr[i].se, INF, i});
for (auto p : edge[i])
{
if (p.se < i) continue;
events.PB({p.fi, i, p.se});
}
hs[i].PB(0);
hs[i].PB(arr[i].se);
}
sort(ALL(events));
reverse(ALL(events));
FOR(i, 0, SZ(events))
{
auto e = events[i];
if (e[1] == INF)
{
s.insert(e[2]); continue;
}
else
{
int u = e[1], v = e[2];
// cerr << u << " -> " << v << endl;
for (auto it = s.UB(u); *it != v; it++)
{
hs[*it].PB(e[0]);
}
hs[u].PB(e[0]);
hs[v].PB(e[0]);
}
}
FOR(i, 0, N)
{
sort(ALL(hs[i]));
hs[i].erase(unique(ALL(hs[i])), hs[i].end());
st[i] = V;
V += SZ(hs[i]);
// cerr << "X COOR " << arr[i].fi << endl;
// for (int x : hs[i])
// {
// cerr << x << ' ';
// }
// cerr << endl;
// cerr << "ST " << i << " = " << st[i] << endl;
}
// cerr << "V = " << V << endl;
st[N] = V;
FOR(i, 0, N)
{
FOR(j, st[i], st[i + 1] - 1)
{
ll dy = hs[i][j + 1 - st[i]] - hs[i][j - st[i]];
edge1[j].PB({dy, j + 1});
edge1[j + 1].PB({dy, j});
}
}
s.clear();
FOR(i, 0, SZ(events))
{
auto e = events[i]; ll h = e[0];
if (e[1] == INF)
{
s.insert(e[2]); continue;
}
else
{
int u = e[1], v = e[2];
for (auto it = s.LB(u); *it != v; it++)
{
int x = *it, y = *(next(it));
int idx = st[x] + LB(ALL(hs[x]), h) - hs[x].begin();
int idy = st[y] + LB(ALL(hs[y]), h) - hs[y].begin();
edge1[idx].PB({arr[y].fi - arr[x].fi, idy});
edge1[idy].PB({arr[y].fi - arr[x].fi, idx});
}
}
}
ans = dijkstra();
return ans;
}
Compilation message
/tmp/ccQsTHop.o: In function `main':
grader.cpp:(.text.startup+0x378): undefined reference to `min_distance(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status
