This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,k,q;
cin >> n >> k >> q;
vector<int> l(n+1);
vector<vector<int>> idxes(k+1);
for(int i=1;i<=n;i++)cin>>l[i];
vector<vector<int>> adj(n+1);
stack<pair<int,int>> s;
for(int i=1;i<=n;i++) {
while(!s.empty() and s.top().first<l[i])s.pop();
if(!s.empty()) {
adj[s.top().second].emplace_back(i);
adj[i].emplace_back(s.top().second);
}
s.emplace(l[i],i);
}
while(!s.empty())s.pop();
for(int i=n;i;i--){
while(!s.empty() and s.top().first<l[i])s.pop();
if(!s.empty()) {
adj[s.top().second].emplace_back(i);
adj[i].emplace_back(s.top().second);
}
s.emplace(l[i],i);
}
for(int i=1;i<=q;i++) {
int a,b;
cin >> a >> b;
vector<bool> visited(n+1);
queue<pair<int,int>> qu;
qu.emplace(-1,a);
while(!qu.empty()) {
auto [dist,idx] = qu.front();qu.pop();
if(visited[idx])continue;
visited[idx]=true;
if(idx==b) {
cout << dist << '\n';
break;
}
for(int&x:adj[idx])if(!visited[x])qu.emplace(dist+1,x);
}
}
}
# | 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... |