#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define mii map<int,int>
#define mll map<long long int, long long int>
#define mivi map<int,vector<int>>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> os;
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
//ifstream cin(".in");
//ofstream cout(".out");
int n,k,q;
cin>>n>>k>>q;
vi v(n);
f0r(i, n)cin>>v[i];
os s;
vpii w(n);
f0r(i, n){
w.pb({v[i], i});
}
sort(w.begin(), w.end());
f0r(i, n){
}
while(q--){
int a,b;
cin>>a>>b;
a--;
b--;
queue<int>q;
q.push(a);
//do we need to calculate l[a] and r[a] for each a to make it faster?
//yes
//insert from low to high, do lowerbound to find left and right?
//pbds probably needed
vi dist(n, 4e18);
dist[a] = 0;
vb vis(n, 0);
vis[a] = 1;
while(!q.empty()){
int node = q.front();
q.pop();
int nl = -1;
int nr = -1;
for(int i = node + 1; i < n; i++){
if(v[i] >= v[node]){
nr = i;
break;
}
}
for(int i = node - 1; i>=0; i--){
if(v[i] >= v[node]){
nl = i;
break;
}
}
if(nl != -1 && !vis[nl]){
q.push(nl);
vis[nl] = 1;
dist[nl] = min(dist[nl], dist[node] + 1);
if(nl == b)break;
}
if(nr != -1 && !vis[nr]){
q.push(nr);
vis[nr] = 1;
dist[nr] = min(dist[nr], dist[node] + 1);
if(nr == b)break;
}
}
cout<<dist[b]-1<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2009 ms |
5980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2047 ms |
6168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
