이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1000006;
const ll INF = 1000000009000000009;
int n;
int x1, y1_;
int x2, y2;
int a[N];
int ul[N], ur[N];
struct ban
{
int x, z;
ll d;
ban(){}
ban(int x, int z, ll d)
{
this->x = x;
this->z = z;
this->d = d;
}
};
bool operator<(const ban& a, const ban& b)
{
return (a.d > b.d);
}
bool c[N][2];
ll d[N][2];
priority_queue<ban> q;
void djk()
{
for (int x = 1; x <= n; ++x)
for (int z = 0; z < 2; ++z)
d[x][z] = INF;
while (1)
{
ban t;
do
{
if (q.empty())
return;
t = q.top();
q.pop();
} while (c[t.x][t.z]);
c[t.x][t.z] = true;
d[t.x][t.z] = t.d;
if (t.z == 0)
{
{
ban h = t;
if (h.x > 1)
{
--h.x;
++h.d;
q.push(h);
}
}
{
ban h = t;
if (h.x < n)
{
++h.x;
++h.d;
q.push(h);
}
}
{
ban h = t;
if (h.x > 1)
{
--h.x;
h.z = 1;
++h.d;
q.push(h);
}
}
}
else
{
{
ban h = t;
if (ul[t.x] >= 1)
{
h.d += abs(t.x - ul[t.x]);
h.x = ul[t.x];
q.push(h);
}
}
{
ban h = t;
if (ur[t.x] <= n)
{
h.d += abs(t.x - ur[t.x]);
h.x = ur[t.x];
q.push(h);
}
}
{
ban h = t;
if (h.x < n)
{
++h.x;
h.z = 0;
++h.d;
q.push(h);
}
}
}
}
}
void solv()
{
cin >> n;
cin >> x1 >> y1_;
cin >> x2 >> y2;
for (int i = 1; i <= n; ++i)
cin >> a[i];
stack<int> s;
for (int i = 1; i <= n; ++i)
{
while (!s.empty() && a[i] <= a[s.top()])
s.pop();
if (s.empty())
ul[i] = 0;
else
ul[i] = s.top();
s.push(i);
}
while (!s.empty())
s.pop();
for (int i = n; i >= 1; --i)
{
while (!s.empty() && a[i] <= a[s.top()])
s.pop();
if (s.empty())
ur[i] = n + 1;
else
ur[i] = s.top();
s.push(i);
}
q.push(ban(x1, 0, abs(y1_ - 1)));
q.push(ban(x1, 1, abs(y1_ - a[x1])));
for (int x = x1; x <= n; ++x)
{
if (a[x] < y1_)
{
q.push(ban(x, 1, abs(x1 - x)));
break;
}
}
for (int x = x1; x >= 1; --x)
{
if (a[x] < y1_)
{
q.push(ban(x, 1, abs(x1 - x)));
break;
}
}
djk();
ll ans = INF;
if (ul[x1] < x2 && x2 < ur[x1])
ans = min(ans, abs(x1 - x2) + 0LL + abs(y1_ - y2));
for (int x = 1; x <= n; ++x)
{
ans = min(ans, d[x][0] + abs(x - x2) + abs(1 - y2));
if (ul[x] < x2 && x2 < ur[x])
ans = min(ans, d[x][1] + abs(x - x2) + abs(a[x] - y2));
}
cout << ans << "\n";
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
ios_base::sync_with_stdio(false), cin.tie(0);
int tt = 1;
//cin >> tt;
while (tt--)
{
solv();
}
return 0;
}
# | 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... |