This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "walk.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>
#include <map>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INTERSECTIONS = 10 + 5;
const llong INF = 1e18;
const int INTINF = 1e9;
const int MAXLOG = 17;
namespace
{
int cnt;
int n, m;
int s, t;
int h[MAXN];
int x[MAXN];
int left[MAXN];
int right[MAXN];
int y[MAXN];
std::map <int,int> map[MAXN];
bool vis[MAXN * INTERSECTIONS];
llong dist[MAXN * INTERSECTIONS];
std::vector <std::pair <int,int>> g[MAXN * INTERSECTIONS];
int cntNodes;
}
struct Sparse
{
int sparse[MAXLOG][MAXN];
int getLOG[MAXN];
void build(int a[])
{
for (int i = 1 ; i <= n ; ++i)
{
sparse[0][i] = a[i];
}
for (int lg = 1 ; (1 << lg) <= n ; ++lg)
{
for (int i = 1 ; i + (1 << lg) - 1 <= n ; ++i)
{
sparse[lg][i] = std::max(sparse[lg - 1][i], sparse[lg - 1][i + (1 << lg - 1)]);
}
}
for (int i = 1 ; i <= n ; ++i)
{
getLOG[i] = getLOG[i - 1];
if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
}
}
int findMAX(int l, int r)
{
int lg = getLOG[r - l + 1];
return std::max(sparse[lg][l], sparse[lg][r - (1 << lg) + 1]);
}
};
Sparse sparse;
llong solve()
{
for (int i = 1 ; i <= n ; ++i)
{
map[i][0] = ++cnt;
}
sparse.build(h);
for (int i = 1 ; i <= m ; ++i)
{
int prev = left[i];
if (map[left[i]][y[i]] == 0)
{
map[left[i]][y[i]] = ++cnt;
}
while (prev < right[i])
{
int l = prev, r = right[i] + 1, mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (sparse.findMAX(prev + 1, mid) < y[i]) l = mid;
else r = mid;
}
if (map[r][y[i]] == 0)
{
map[r][y[i]] = ++cnt;
}
// std::cout << "here: " << prev << ' ' << r << ' ' << y[i] << '\n';
g[map[prev][y[i]]].push_back({map[r][y[i]], x[r] - x[prev]});
g[map[r][y[i]]].push_back({map[prev][y[i]], x[r] - x[prev]});
prev = r;
}
}
for (int i = 1 ; i <= n ; ++i)
{
auto prev = map[i].begin();
for (auto curr = std::next(map[i].begin()) ; curr != map[i].end() ; ++curr)
{
// std::cout << "edge ver: " << x[i] << ' ' << prev->first << ' ' << x[i] << ' ' << curr->first << '\n';
g[prev->second].push_back({curr->second, curr->first - prev->first});
g[curr->second].push_back({prev->second, curr->first - prev->first});
prev = curr;
}
}
std::priority_queue <std::pair <llong,int>> pq;
std::fill(dist + 1, dist + 1 + cnt, INF);
pq.push({0, map[s][0]});
dist[map[s][0]] = 0;
while (pq.size())
{
auto [d, node] = pq.top();
pq.pop();
if (vis[node])
{
continue;
}
vis[node] = true;
for (const auto &[u, ed] : g[node])
{
if (dist[u] > dist[node] + ed)
{
dist[u] = dist[node] + ed;
pq.push({-dist[u], u});
}
}
}
return (dist[map[t][0]] == INF ? -1 : dist[map[t][0]]);
}
llong dpL[MAXN];
llong dpR[MAXN];
llong solveSpecial()
{
for (int i = 1 ; i <= m ; ++i)
{
if (left[i] == 1)
{
dpL[i] = y[i];
dpR[i] = y[i] + x[right[i]];
} else
{
dpL[i] = INF;
dpR[i] = INF;
for (int j = 1 ; j < i ; ++j)
{
if (right[j] >= left[i])
{
if (y[j] < y[i])
{
dpL[i] = std::min(dpL[i], dpL[j] + x[left[i]] - x[left[j]] + y[i] - y[j]);
}
if (y[j] >= y[i] && y[j] <= h[left[i]])
{
dpL[i] = std::min(dpL[i], dpL[j] + x[left[i]] - x[left[j]] + y[j] - y[i]);
}
}
if (right[j] >= left[i] && right[j] <= right[i])
{
if (y[j] >= y[i])
{
dpR[i] = std::min(dpR[i], dpR[j] + y[j] - y[i] + x[right[i]] - x[right[j]]);
}
if (y[j] <= y[i] && y[i] <= h[right[i]])
{
dpR[i] = std::min(dpR[i], dpR[j] + y[i] - y[j] + x[right[i]] - x[right[j]]);
}
}
}
dpR[i] = std::min(dpR[i], dpL[i] + x[right[i]] - x[left[i]]);
}
}
llong ans = INF;
for (int i = 1 ; i <= m ; ++i)
{
if (right[i] == n)
{
ans = std::min(ans, dpR[i] + y[i]);
}
}
return ans;
}
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 t)
{
n = x.size();
m = l.size();
::s = s + 1; ::t = t + 1;
for (int i = 0 ; i < n ; ++i)
{
::h[i + 1] = h[i];
::x[i + 1] = x[i];
}
std::vector <int> perm(m);
std::iota(perm.begin(), perm.end(), 0);
std::sort(perm.begin(), perm.end(), [&](int x, int y)
{
return l[x] < l[y];
});
for (int i = 0 ; i < m ; ++i)
{
::left[i + 1] = l[perm[i]] + 1;
::right[i + 1] = r[perm[i]] + 1;
::y[i + 1] = y[perm[i]];
}
if (::s == 1 && ::t == n) return solveSpecial();
return solve();
}
Compilation message (stderr)
walk.cpp: In member function 'void Sparse::build(int*)':
walk.cpp:51:89: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
51 | sparse[lg][i] = std::max(sparse[lg - 1][i], sparse[lg - 1][i + (1 << lg - 1)]);
| ~~~^~~
walk.cpp:58:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
58 | if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
| ~~~~~~~~~~^~~
walk.cpp: In function 'llong solve()':
walk.cpp:91:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | mid = l + r >> 1;
| ~~^~~
walk.cpp: At global scope:
walk.cpp:32:9: warning: '{anonymous}::cntNodes' defined but not used [-Wunused-variable]
32 | int cntNodes;
| ^~~~~~~~
# | 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... |