#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; ll sx, sy, tx, ty;
cin >> n >> sx >> sy >> tx >> ty;
sx--, sy--, tx--, ty--;
vector<ll> a(n);
for (auto& x : a) cin >> x;
auto engiin = [&](ll x1, ll y1, ll x2, ll y2) -> ll {
ll y = y1, p = min(x1, x2), q = max(x1, x2);
FOR(i, p, q) y = min(y, a[i]);
ll ans = q - p + abs(y - y2);
if (y <= y2) return ans;
ROF(i, p - 1, 0) {
ans = min(ans, x1 - i + x2 - i + abs(a[i] - y2));
if (a[i] < y2) break;
}
FOR(i, q + 1, n - 1) {
ans = min(ans, i - x2 + i - x1 + abs(a[i] - y2));
if (a[i] < y2) break;
}
return ans;
};
vector dis(n, vector<ll>(2));
FOR(i, 0, n - 1) dis[i] = {engiin(sx, sy, i, 0), engiin(sx, sy, i, a[i])};
priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
FOR(i, 0, n - 1) {
if (i) dis[i][0] = min(dis[i][0], dis[i - 1][1] + 1);
pq.push({dis[i][0], i});
}
for (; !pq.empty(); pq.pop()) {
auto [d, i] = pq.top();
if (d != dis[i][0]) continue;
if (i && d + 1 < dis[i - 1][0]) pq.push({dis[i - 1][0] = d + 1, i - 1});
if (i + 1 < n && d + 1 < dis[i + 1][0]) pq.push({dis[i + 1][0] = d + 1, i + 1});
}
FOR(i, 0, n - 2) dis[i][1] = min(dis[i][1], dis[i + 1][0] + 1);
ll ans = engiin(sx, sy, tx, ty);
FOR(i, 0, n - 1) {
ans = min(ans, dis[i][0] + engiin(i, 0, tx, ty));
ans = min(ans, dis[i][1] + engiin(i, a[i], tx, ty));
}
cout << ans << "\n";
return 6/22;
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |