#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e5 + 5;
const int LOG = 20;
int p[2][LOG][MXN];
int sp[2][LOG][MXN];
vector<int> h;
void init(int N, vector<int> H)
{
h = H;
int prv[N], nxt[N];
{
vector<int> st;
for (int i = 0; i < N; i++)
{
while (!st.empty() && H[i] > H[st.back()]) st.pop_back();
if (st.empty()) prv[i] = -1;
else prv[i] = st.back();
st.push_back(i);
}
}
{
vector<int> st;
for (int i = N - 1; i >= 0; i--)
{
while (!st.empty() && H[i] > H[st.back()]) st.pop_back();
if (st.empty()) nxt[i] = -1;
else nxt[i] = st.back();
st.push_back(i);
}
}
for (int i = 0; i < N; i++)
{
p[0][0][i] = p[1][0][i] = -1;
sp[0][0][i] = prv[i], sp[1][0][i] = nxt[i];
if (nxt[i] != -1 && prv[i] != -1)
{
p[0][0][i] = nxt[i], p[1][0][i] = prv[i];
if (H[nxt[i]] > H[prv[i]]) swap(p[0][0][i], p[1][0][i]);
}
else p[0][0][i] = max(nxt[i], prv[i]);
}
for (int _ = 0; _ < 2; _++)
{
for (int i = 1; i < LOG; i++)
{
for (int j = 0; j < N; j++)
{
if (p[_][i - 1][j] == -1)
{
p[_][i][j] = -1;
continue;
}
p[_][i][j] = p[_][i - 1][p[_][i - 1][j]];
}
}
for (int i = 1; i < LOG; i++)
{
for (int j = 0; j < N; j++)
{
if (sp[_][i - 1][j] == -1)
{
sp[_][i][j] = -1;
continue;
}
sp[_][i][j] = sp[_][i - 1][sp[_][i - 1][j]];
}
}
}
}
int dist(int A, int C)
{
int res = 0;
for (int _ = 1; _ >= 0 && A != C; _--)
{
for (int i = LOG - 1; i >= 0; i--)
{
if (p[_][i][A] == -1) continue;
if (h[p[_][i][A]] >= h[C]) continue;
A = p[_][i][A];
res += (1 << i);
}
if (p[_][0][A] != -1 && h[p[_][0][A]] <= h[C])
{
A = p[_][0][A];
res++;
}
}
if (A != C) return -1;
return res;
}
int minimum_jumps(int A, int B, int C, int D)
{
int X = C;
for (int i = LOG - 1; i >= 0; i--)
{
if (sp[1][i][X] == -1 || sp[1][i][X] > D) continue;
X = sp[1][i][X];
}
for (int i = LOG - 1; i >= 0; i--)
{
if (sp[0][i][B] == -1 || sp[0][i][B] < A) continue;
if (dist(sp[0][i][B], X) == -1) continue;
B = sp[0][i][B];
}
if (!(sp[0][0][B] == -1 || sp[0][0][B] < A || dist(sp[0][0][B], X) == -1)) B = sp[0][0][B];
for (int i = LOG - 1; i >= 0; i--)
{
if (sp[1][i][C] == -1 || sp[1][i][C] > D) continue;
if (dist(B, sp[1][i][C]) != -1) continue;
C = sp[1][i][C];
}
if (!(sp[1][0][C] == -1 || sp[1][0][C] > D || dist(B, sp[1][0][C]) == -1) && dist(B, C) == -1) C = sp[1][0][C];
return dist(B, C);
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |