/**
* 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;
const int lg = 20;
int uly[N+2][lg], kici[N+2][lg];
vector<int> hh;
int idx[N+2];
int nn;
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)
for (int j = 0; j < lg; ++j)uly[i][j] = kici[i][j] = N+1;
for (int i = 0; i < lg; ++i)uly[N+1][i] = kici[N+1][i] = N+1;
for (int i = 0; i < n; ++i) {
if (a[i] == -1 && b[i] == -1)uly[i][0] = kici[i][0] = i;
else if (a[i] == -1)uly[i][0] = b[i], kici[i][0] = b[i];
else if (b[i] == -1)uly[i][0] = a[i], kici[i][0] = a[i];
else if (h[a[i]] > h[b[i]])uly[i][0] = a[i], kici[i][0] = b[i];
else uly[i][0] = b[i], kici[i][0] = a[i];
}
for (int i = 0; i < n; ++i) {
hh.push_back(h[i]);
idx[h[i]] = i;
}
sort(h.rbegin(), h.rend());
for (int i = 0; i < n; ++i) {
for (int j = 1; j < lg; ++j) {
//if (uly[i][j-1] != i)
int ind = idx[h[i]];
uly[ind][j] = uly[uly[ind][j-1]][j-1];
//if (kici[i][j-1] != i)
kici[ind][j] = kici[kici[ind][j-1]][j-1];
};
}
}
int minimum_jumps(int a, int b, int c, int d) {
d = hh[c];
if (hh[a] > d)return -1;
int ans = 0;
for (int i = 19; i >= 0; --i) {
if ((i > 0 && uly[a][i] == uly[a][i-1]) || uly[a][i] == a)continue;
if (uly[a][i] <= d) {
//cout << a << " " << i << " " << uly[a][i] << nl;
a = idx[uly[a][i]];
ans += (1 << i);
}
}
if (a == c)return ans;
for (int i = 19; i >= 0; --i) {
if (i > 0 && kici[a][i] == kici[a][i-1])continue;
if (kici[a][i] <= d) {
a = idx[kici[a][i]];
ans += (1 << i);
}
}
if (a == d)return ans;
return -1;
}
//int main() {
//int n, q; cin >> n >> q;
//vector<int> h(n);
//for (int i = 0; i < n; ++i)cin >> h[i];
//init(n, h);
//while (q--) {
//int a, b, c, d; cin >> a >> b >> c >> d;
//cout << minimum_jumps(a, b, c, d) << nl;
//}
//}
# | 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... |