#include<bits/stdc++.h>
using namespace std;
const int lg=4;
typedef pair<int,int> pii;
int n,k,q;
int a[100001];
int l[100001],r[100001];
int sl[18][100001],sr[18][100001];
int find(int id,int val){
if(val==id) return 0;
int x=0;
int bl=id,br=id,nl,nr;
for(int i=lg; i>=0 ;i--){
x|=(1<<i);
nl=min(sl[i][bl],sl[i][br]);
nr=max(sr[i][bl],sr[i][br]);
if(nl<=val && val<=nr) x^=(1<<i);
else bl=nl,br=nr;
}
x++;
nl=min(sl[0][bl],sl[0][br]);
nr=max(sr[0][bl],sr[0][br]);
if(nl==val || nr==val) return x;
else return 1e9;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> k >> q;
for(int i=1; i<=n ;i++) cin >> a[i];
stack<int>s;
for(int i=1; i<=n ;i++){
while(!s.empty() && a[s.top()]<a[i]) s.pop();
if(!s.empty()) l[i]=s.top();
else l[i]=i;
s.push(i);
}
while(!s.empty()) s.pop();
for(int i=n; i>=1 ;i--){
while(!s.empty() && a[s.top()]<a[i]) s.pop();
if(!s.empty()) r[i]=s.top();
else r[i]=i;
s.push(i);
}
for(int i=1; i<=n ;i++){
sl[0][i]=l[i];sr[0][i]=r[i];
}
for(int j=1; j<=lg ;j++){
for(int i=1; i<=n ;i++){
sl[j][i]=min(sl[j-1][sl[j-1][i]],sl[j-1][sr[j-1][i]]);
sr[j][i]=max(sr[j-1][sl[j-1][i]],sr[j-1][sr[j-1][i]]);
}
}
for(int i=1; i<=q ;i++){
int u,v;cin >> u >> v;
if(u>v) swap(u,v);
if(l[v]==u || r[u]==v){
cout << "0\n";
continue;
}
int x=0,y,ans=1e9;
int bl=u,br=u,nl,nr;
for(int j=lg; j>=0 ;j--){
x|=(1<<j);
nl=min(sl[j][bl],sl[j][br]);
nr=max(sr[j][bl],sr[j][br]);
y=find(v,nl);
if(y==1e9) bl=nl,br=nr;
else x^=(1<<j);
}
x++;
nl=min(sl[0][bl],sl[0][br]);
nr=max(sr[0][bl],sr[0][br]);
y=find(v,nl);
ans=min(ans,x+y);
x=0,bl=u,br=u;
for(int j=lg; j>=0 ;j--){
x|=(1<<j);
nl=min(sl[j][bl],sl[j][br]);
nr=max(sr[j][bl],sr[j][br]);
y=find(v,nr);
if(y==1e9) bl=nl,br=nr;
else x^=(1<<j);
}
x++;
nl=min(sl[0][bl],sl[0][br]);
nr=max(sr[0][bl],sr[0][br]);
y=find(v,nr);
ans=min(ans,x+y);
cout << ans-1 << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
5760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
271 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
281 ms |
7488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
