#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define loop(n, i) for (int i = 0; i < n; i++)
#define pb push_back
#define sz(x) (int)(x).size()
typedef pair<int, int> ii;
typedef vector<int32_t> vi32;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef set<ii> sii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef vector<vi32> vvi32;
i64 INF = 1e18;
i64 min_distance(vi32 x, vi32 h, vi32 l, vi32 r, vi32 y, int32_t s, int32_t g)
{
int n = sz(x), m = sz(l);
vvi32 endsHere(n), startHere(n);
loop(m, i) endsHere[r[i]].pb(i);
loop(m, i) startHere[l[i]].pb(i);
vi64 dis(m, INF);
sii active; // {y, ix}
i64 res = INF;
for (int p = 0; p < n; p++)
{
for (int i : startHere[p])
{
int y2 = y[i];
auto nxt = active.lower_bound({y2, 0});
if (nxt != active.end())
{
auto [y1, j] = *nxt;
dis[i] = min(dis[i], dis[j] + abs(y1 - y2));
}
if (nxt != begin(active))
{
auto [y1, j] = *--nxt;
dis[i] = min(dis[i], dis[j] + abs(y1 - y2));
}
}
for (int i : startHere[p])
{
active.insert({y[i], i});
if (p == 0)
dis[i] = y[i];
}
if (p == g)
{
for (auto [y1, i] : active)
{
res = min(res, dis[i] + y1);
}
}
for (int i : endsHere[p])
{
active.erase({y[i], i});
}
}
if (res == INF)
return -1;
return res + x.back();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |