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 <bits/stdc++.h>
struct SG {
int h, l, r;
SG() { }
SG(int a, int b, int c) : h(a) , l(b) , r(c) { }
};
int n, m;
std::vector <std::pair <int, int>> g[2];
std::vector <std::vector <std::pair <int, int>>> gg;
std::vector <std::vector <int>> del[2];
std::vector <int> h;
std::vector <SG> sg;
void fix(int node) {
std::vector <std::pair <int, int>> dir[2];
dir[0] = dir[1] = { { h[node], node } };
for (int i = node + 1; i < n; i++) {
if (h[i] <= dir[1].back().first) {
continue;
}
dir[1].emplace_back(h[i], i);
}
for (int i = node - 1; i >= 0; i--) {
if (h[i] <= dir[0].back().first) {
continue;
}
dir[0].emplace_back(h[i], i);
}
auto cop = sg;
cop.clear();
for (const auto& s : sg) {
if (s.l < node && node < s.r) {
int lb[2] = {
(int) (std::lower_bound(dir[0].begin(), dir[0].end(), std::make_pair(s.h, -1)) - dir[0].begin()),
(int) (std::lower_bound(dir[1].begin(), dir[1].end(), std::make_pair(s.h, -1)) - dir[1].begin())
};
if (s.l != dir[0][lb[0]].second) {
cop.emplace_back(s.h, s.l, dir[0][lb[0]].second);
}
if (dir[0][lb[0]].second != dir[1][lb[1]].second) {
cop.emplace_back(s.h, dir[0][lb[0]].second, dir[1][lb[1]].second);
}
if (dir[1][lb[1]].second != s.r) {
cop.emplace_back(s.h, dir[1][lb[1]].second, s.r);
}
} else {
cop.emplace_back(s);
}
}
sg = cop;
}
long long min_distance(std::vector <int> a, std::vector <int> _h, std::vector <int> l, std::vector <int> r, std::vector <int> y, int f, int t) {
n = a.size();
m = l.size();
sg.resize(m);
h = _h;
for (int i = 0; i < m; i++) {
sg[i] = { y[i], l[i], r[i] };
}
fix(f);
fix(t);
del[0].resize(4'000'000);
del[1].resize(4'000'000);
for (const auto& s : sg) {
del[0][s.l].emplace_back(s.h);
del[1][s.r].emplace_back(s.h);
}
std::multiset <int> st = { 0 };
for (int i = 0; i < n; i++) {
for (int x : del[0][i]) {
st.insert(x);
}
for (int k = 0; k < 2; k++) {
for (int x : del[k][i]) {
g[0].emplace_back(a[i], x);
g[0].emplace_back(a[i], *prev(st.lower_bound(x)));
}
}
for (int x : del[1][i]) {
st.erase(st.find(x));
}
}
std::sort(g[0].begin(), g[0].end());
for (auto p : g[0]) {
if (g[1].empty() || g[1].back() != p) {
g[1].push_back(p);
}
}
g[0] = g[1];
g[1].clear();
for (auto p : g[0]) {
g[1].emplace_back(p.second, p.first);
}
std::sort(g[1].begin(), g[1].end());
gg.resize(4'000'000);
for (int i = 1; i < (int) g[0].size(); i++) {
if (g[0][i - 1].first != g[0][i].first) {
continue;
}
gg[i - 1].emplace_back(i - 0, g[0][i].second - g[0][i - 1].second);
gg[i - 0].emplace_back(i - 1, g[0][i].second - g[0][i - 1].second);
}
for (const auto& s : sg) {
int lb = std::lower_bound(g[1].begin(), g[1].end(), std::make_pair(s.h, a[s.l])) - g[1].begin();
while (g[1][lb] != (std::pair <int, int>) { s.h, a[s.r] }) {
std::pair <int, int> p[2] = {
{ g[1][lb - 0].second, g[1][lb - 0].first },
{ g[1][lb + 1].second, g[1][lb + 1].first }
};
lb++;
gg[std::lower_bound(g[0].begin(), g[0].end(), p[0]) - g[0].begin()].emplace_back(std::lower_bound(g[0].begin(), g[0].end(), p[1]) - g[0].begin(), p[1].first - p[0].first);
gg[std::lower_bound(g[0].begin(), g[0].end(), p[1]) - g[0].begin()].emplace_back(std::lower_bound(g[0].begin(), g[0].end(), p[0]) - g[0].begin(), p[1].first - p[0].first);
}
}
std::vector <long long> dd(4'000'000, 1LL << 60);
std::priority_queue <std::pair <long long, int>> pq;
{
int tmp = std::lower_bound(g[0].begin(), g[0].end(), std::make_pair(a[f], 0)) - g[0].begin();
if (tmp == (int) g[0].size() || g[0][tmp] != (std::pair <int, int>) { a[f], 0 }) {
return -1;
}
pq.push({ dd[tmp] = 0, tmp });
}
while (pq.size()) {
int v = pq.top().second;
pq.pop();
for (auto p : gg[v]) {
if (dd[p.first] <= dd[v] + p.second) {
continue;
}
dd[p.first] = dd[v] + p.second;
pq.push({ -dd[p.first], p.first });
}
}
int lb = std::lower_bound(g[0].begin(), g[0].end(), std::make_pair(a[t], 0)) - g[0].begin();
return lb == (int) g[0].size() || g[0][lb] != (std::pair <int, int>) { a[t], 0 } || dd[lb] == (1LL << 60) ? -1LL : dd[lb];
}
# | 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... |