#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, q;
cin >> n >> k >> q;
vector<int> lvl(n);
vector<int> adj[n];
for(int i=0;i<n;i++)
cin >> lvl[i];
int lft[n], rgt[n];
stack<int> s;
for(int i=0;i<n;i++) {
while(s.size() && lvl[s.top()] < lvl[i])
s.pop();
lft[i] = (s.size()?s.top():-1);
s.push(i);
}
while(s.size())
s.pop();
for(int i=n;i--;) {
while(s.size() && lvl[s.top()] < lvl[i])
s.pop();
rgt[i] = (s.size()?s.top():-1);
s.push(i);
}
vector<int> swp(n, 0);
for(int i=0;i<n;i++) {
if(rgt[i] != -1) {
swp[i+1] ^= 1;
swp[rgt[i]] ^= 1;
}
if(lft[i] != -1 && lvl[lft[i]] != lvl[i]) {
swp[lft[i]+1] ^= 1;
swp[i] ^= 1;
}
}
partial_sum(swp.begin(),swp.end(),swp.begin());
auto cmp = [&lvl,&swp](int x, int y) -> bool {
if(lvl[x] != lvl[y])
return lvl[x] < lvl[y];
if(swp[x] & 1)
return x > y;
return x < y;
};
for(int i=0;i<n;i++) {
if(lft[i] == -1 || cmp(lft[i], i))
lft[i] = rgt[i];
if(rgt[i] == -1 || cmp(rgt[i], i))
rgt[i] = lft[i];
if(lft[i] != -1 && cmp(rgt[i], lft[i]))
swap(lft[i], rgt[i]);
}
int height[n];
memset(height,0,sizeof(height));
int ord[n];
iota(ord,ord+n,0);
sort(ord,ord+n,cmp);
for(int i=n-1;i--;)
height[ord[i]] = height[lft[ord[i]]] + 1;
while(q--) {
int a, b, l;
cin >> a >> b;
a--; b--;
int ans = 0;
l = a;
for(int c=a,d=b;c!=d;) {
if(height[c] > height[d])
swap(c, d);
l = d = lft[d];
}
while(rgt[a] != -1 && height[l] <= height[rgt[a]])
a = rgt[a], ans++;
while(rgt[b] != -1 && height[l] <= height[rgt[b]])
b = rgt[b], ans++;
int dir = height[a] + height[b] - 2 * height[l];
int liftA = ~rgt[a] ? abs(height[rgt[a]] - height[b]) + 1 : 1e7;
int liftB = ~rgt[b] ? abs(height[rgt[b]] - height[a]) + 1 : 1e7;
int liftBoth = ~rgt[a] && ~rgt[b] ? abs(height[rgt[a]] - height[rgt[b]]) + 2 : 1e7;
cout << ans + min({dir,liftA,liftB,liftBoth})-1 << "\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... |