#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> h;
vector<int> minV;
vector<int> maxV;
vector<vector<int>> liftingMin;
vector<vector<int>> liftingMax;
void init(int N, std::vector<int> H) {
n = N, h = H;
minV = maxV = vector<int>(n);
liftingMin = liftingMax = vector<vector<int>>(n, vector<int>(30, -1));
{
stack<pair<int, int>> st;
st.push({1e9, -1});
for (int i = 0; i < n; i++) {
while (st.top().first < h[i]) st.pop();
minV[i] = st.top().second;
st.push({h[i], i});
}
}
{
stack<pair<int, int>> st;
st.push({1e9, -1});
for (int i = n-1; i >= 0; i--) {
while (st.top().first < h[i]) st.pop();
maxV[i] = st.top().second;
st.push({h[i], i});
}
}
//for (int x : minV) cout << x << " "; cout << endl;
//for (int x : maxV) cout << x << " "; cout << endl;
//return;
for (int i = 0; i < n; i++) {
if (minV[i] == -1 && maxV[i] == -1) continue;
if (minV[i] == -1) {
minV[i] = maxV[i];
} else if (maxV[i] == -1) {
maxV[i] = minV[i];
} else if (h[minV[i]] > h[maxV[i]]) swap(minV[i], maxV[i]);
}
//for (int x : minV) cout << x << " "; cout << endl;
//for (int x : maxV) cout << x << " "; cout << endl;
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) v.push_back({h[i], i});
sort(v.rbegin(), v.rend());
for (int j = 1; j < n; j++) {
int i = v[j].second;
liftingMin[i][0] = minV[i];
liftingMax[i][0] = maxV[i];
for (int j = 1; j < 30; j++) {
if (liftingMin[i][j-1] != -1) liftingMin[i][j] = liftingMin[liftingMin[i][j-1]][j-1];
if (liftingMax[i][j-1] != -1) liftingMax[i][j] = liftingMax[liftingMax[i][j-1]][j-1];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 5; j++) cout << liftingMax[i][j] << " ";
cout << endl;
}
}
pair<int, int> blift(vector<vector<int>>& g, int u, int v) {
for (int i = -1; i < 30; i++) {
if (g[u][i + 1] == -1 || h[g[u][i + 1]] > h[v]) {
if (i == -1) return {0, u};
else return {(1<<i) + blift(g, g[u][i], v).first, g[u][i]};
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (A == B && C == D) {
A--, B--, C--, D--;
pair<int, int> p = blift(liftingMax, A, D);
pair<int, int> q = blift(liftingMin, p.second, D);
if (h[q.second] != h[D]) return -1;
else return p.first + q.first;
}
return 0;
}
//7 0
//3 2 1 6 4 5 7
int main2() {
int N, Q;
//assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
N = 7;
Q = 10000;
H = vector<int>{3, 2, 1, 6, 4, 5, 7};
for (int i = 0; i < N; ++i) {
//assert(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i) {
int A, B, C, D;
assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
printf("%d\n", minimum_jumps(A, B, C, D));
}
return 0;
}
Compilation message
jumps.cpp: In function 'std::pair<int, int> blift(std::vector<std::vector<int> >&, int, int)':
jumps.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
76 | }
| ^
jumps.cpp: In function 'int main2()':
jumps.cpp:95:23: warning: 'N' is used uninitialized in this function [-Wuninitialized]
95 | std::vector<int> H(N);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
