#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 10;
int n, k, q;
int l[N];
const int LG = 16;
int L[N][LG + 1], R[N][LG + 1];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k >> q;
for (int i = 1; i <= n; ++i) cin >> l[i];
{ // RMQ
{ // left
stack<int> st;
for (int i = 1; i <= n; ++i) {
while (st.size() && l[st.top()] < l[i]) st.pop();
L[i][0] = (!st.size() ? 1 : st.top());
st.push(i);
}
}
{ // right
stack<int> st;
for (int i = n; i >= 1; --i) {
while (st.size() && l[st.top()] < l[i]) st.pop();
R[i][0] = (!st.size() ? n : st.top());
st.push(i);
}
}
for (int j = 1; j <= LG; ++j) {
for (int i = 1; i <= n; ++i) {
L[i][j] = min(L[L[i][j - 1]][j - 1], L[R[i][j - 1]][j - 1]);
R[i][j] = max(R[L[i][j - 1]][j - 1], R[R[i][j - 1]][j - 1]);
}
}
}
while (q--) {
int a, b; cin >> a >> b;
if (a > b) swap(a, b);
int answer = 0;
int l = a, r = a;
for (int i = LG; i >= 0; --i) {
if (max(R[l][i], R[r][i]) < b) {
tie(l, r) = make_pair(min(L[l][i], L[r][i]), max(R[l][i], R[r][i]));
answer += (1 << i);
}
}
int preR = r;
l = b, r = b;
for (int i = LG; i >= 0; --i) {
if (min(L[l][i], L[r][i]) > preR) {
tie(l, r) = make_pair(min(L[l][i], L[r][i]), max(R[l][i], R[r][i]));
answer += (1 << i);
}
}
cout << answer << "\n";
}
}
# | 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... |