/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
//#include "jumps.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
//#define int ll
const char nl = '\n';
const int N = 2e5;
const int inf = 1e9;
vector<int> g[N+1];
int nn;
bool ok = true;
void init(int n, vector<int> h) {
nn = n;
stack<int> st;
vector<int> a(n, -1), b(n, -1);
for (int i = n-1; i >= 0; --i) {
while (!st.empty() && h[st.top()] <= h[i])st.pop();
if (!st.empty())a[i] = st.top();
st.push(i);
}
while (!st.empty())st.pop();
for (int i = 0; i < n; ++i) {
while (!st.empty() && h[st.top()] <= h[i])st.pop();
if (!st.empty())b[i] = st.top();
st.push(i);
}
for (int i = 0; i < n; ++i) {
if (i > 0 && h[i] <= h[i-1])ok = false;
if (a[i] != -1)g[i].push_back(a[i]);
if (b[i] != -1)g[i].push_back(b[i]);
}
}
int minimum_jumps(int a, int b, int c, int d) {
if (ok)return c-b;
queue<pair<int, int>> q;
vector<int> vis(nn+1);
for (int i = a; i <= b; ++i) {
q.push({0, i});
vis[i] = 1;
}
int ans = inf;
while (!q.empty()) {
int u = q.front().second, w = q.front().first;
q.pop();
if (w >= ans)continue;
if (u >= c && u <= d) {
ans = min(ans, w);
continue;
}
for (auto i: g[u]) {
if (!vis[i])
q.push({w+1, i});
}
}
if (ans == inf)ans = -1;
return ans;
}
# | 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... |