#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
const ll M=2e5+10;
const ll inf=2e18;
ll n,k,q,l[M],dis[M];
vii lev[M],v[M];
set<ll>s;
void bfs(ll x){
for(int i=1;i<=n;i++)
dis[i]=inf;
dis[x]=0;
queue<ll>q;
q.push(x);
while(!q.empty()){
ll p=q.front();
q.pop();
for(auto it:v[p]){
if(dis[it]==inf)
dis[it]=dis[p]+1,q.push(it);
}
}
}
void add(ll x,ll y,ll z){
auto it=s.upper_bound(-x);
auto itt=s.upper_bound(x);
ll nxt,prev;
nxt=prev=inf;
if(itt!=s.end()){
nxt=*itt;
}
if(it!=s.end()&&*it<0){
prev=-*it;
}
if(nxt!=inf){
if(y<nxt)
v[x].pb(y),v[y].pb(x);
else
v[x].pb(nxt),v[nxt].pb(x);
}
else if(y!=inf)
v[x].pb(y),v[y].pb(x);
if(prev!=inf){
if(z<prev)
v[x].pb(prev),v[prev].pb(x);
}
s.insert(x),s.insert(-x);
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin>>n>>k>>q;
for(int i=0;i<n;i++)
cin>>l[i+1],lev[l[i+1]].pb(i+1);
for(int i=k;i>=1;i--){
for(int j=0;j<lev[i].size();j++){
ll y,z;
y=inf,z=-inf;
if(j>0)
z=lev[i][j-1];
if(j<lev[i].size()-1)
y=lev[i][j+1];
add(lev[i][j],y,z);
}
}
while(q--){
ll a,b;
cin>>a>>b;
bfs(a);
cout<<dis[b]-1<<'\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9816 KB |
Output is correct |
2 |
Correct |
4 ms |
9820 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9816 KB |
Output is correct |
5 |
Correct |
6 ms |
9820 KB |
Output is correct |
6 |
Correct |
5 ms |
9820 KB |
Output is correct |
7 |
Correct |
6 ms |
9824 KB |
Output is correct |
8 |
Correct |
6 ms |
9860 KB |
Output is correct |
9 |
Correct |
4 ms |
9820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9820 KB |
Output is correct |
2 |
Correct |
216 ms |
26704 KB |
Output is correct |
3 |
Correct |
253 ms |
27172 KB |
Output is correct |
4 |
Correct |
239 ms |
27216 KB |
Output is correct |
5 |
Correct |
260 ms |
27388 KB |
Output is correct |
6 |
Correct |
268 ms |
27512 KB |
Output is correct |
7 |
Correct |
294 ms |
29008 KB |
Output is correct |
8 |
Correct |
172 ms |
24780 KB |
Output is correct |
9 |
Correct |
129 ms |
26456 KB |
Output is correct |
10 |
Correct |
125 ms |
25780 KB |
Output is correct |
11 |
Correct |
231 ms |
27188 KB |
Output is correct |
12 |
Correct |
224 ms |
26960 KB |
Output is correct |
13 |
Correct |
238 ms |
26708 KB |
Output is correct |
14 |
Correct |
257 ms |
27448 KB |
Output is correct |
15 |
Correct |
231 ms |
26892 KB |
Output is correct |
16 |
Correct |
222 ms |
26704 KB |
Output is correct |
17 |
Correct |
254 ms |
28024 KB |
Output is correct |
18 |
Correct |
235 ms |
28044 KB |
Output is correct |
19 |
Correct |
270 ms |
30424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2064 ms |
27180 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2009 ms |
29160 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |