#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
//~ #define int ll
const int N = 2e5 + 5;
const int K = 20;
vector<int> edges[N];
int a[N], L[N], R[N], pos[N][K];
ar<int, 2> l[N][K], r[N][K];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, k, q; cin >> n >> k >> q;
vector<int> ss;
memset(L, -1, sizeof L);
memset(R, -1, sizeof R);
for(int i=0;i<n;i++){
cin >> a[i]; a[i]--;
while(!ss.empty() && a[ss.back()] < a[i]){
ss.pop_back();
}
if(!ss.empty()){
L[i] = ss.back();
}
ss.push_back(i);
}
ss.clear();
for(int i=n-1;~i;i--){
while(!ss.empty() && a[ss.back()] < a[i]){
ss.pop_back();
}
if(!ss.empty()){
R[i] = ss.back();
}
ss.push_back(i);
}
memset(l, 63, sizeof l);
memset(r, 63, sizeof r);
for(int i=0;i<n;i++){
l[i][0] = r[i][0] = {i, 0};
pos[i][0] = i;
}
for(int j=1;j<k;j++){
for(int i=0;i<n;i++){
auto [p, c] = l[i][j-1];
if(a[p] >= j) l[i][j] = {p, c};
else if(i != p) l[i][j] = {l[p][j][0], l[p][j][1] + c};
else if(~L[i]){
l[i][j] = l[L[i]][j]; l[i][j][1]++;
} else assert(false);
}
for(int i=n-1;~i;i--){
auto [p, c] = r[i][j-1];
if(a[p] >= j) r[i][j] = {p, c};
else if(i != p) r[i][j] = {r[p][j][0], r[p][j][1] + c};
else if(~R[i]){
r[i][j] = r[R[i]][j]; r[i][j][1]++;
} else assert(false);
}
for(int i=0;i<n;i++){
l[i][j][1] = min(l[i][j][1], l[r[i][j-1][0]][j][1] + r[i][j-1][1] + (a[r[i][j-1][0]] >= j));
r[i][j][1] = min(r[i][j][1], r[l[i][j-1][0]][j][1] + l[i][j-1][1] + (a[l[i][j-1][0]] >= j));
}
int last = 0;
for(int i=0;i<n;i++){
if(a[i] >= j) pos[i][j] = last++;
}
}
//~ for(int j=0;j<k;j++){
//~ for(int i=0;i<n;i++){
//~ cout<<l[i][j][0]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int j=0;j<k;j++){
//~ for(int i=0;i<n;i++){
//~ cout<<l[i][j][1]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int j=0;j<k;j++){
//~ for(int i=0;i<n;i++){
//~ cout<<r[i][j][0]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int j=0;j<k;j++){
//~ for(int i=0;i<n;i++){
//~ cout<<r[i][j][1]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
auto check = [&](int j, ar<int, 2> a, ar<int, 2> b){
if(a[0] > n || b[0] > n) assert(false);
//~ cout<<j<<" "<<a[0]<<" "<<b[0]<<" "<<abs(pos[a[0]][j] - pos[b[0]][j])<<" "<<a[1] + b[1]<<"\n";
return abs(pos[a[0]][j] - pos[b[0]][j]) + a[1] + b[1];
};
while(q--){
int a, b; cin >> a >> b;
a--, b--;
int res = 1e9;
for(int j=0;j<k;j++){
res = min(res, check(j, l[a][j], l[b][j]));
res = min(res, check(j, l[a][j], r[b][j]));
res = min(res, check(j, r[a][j], l[b][j]));
res = min(res, check(j, r[a][j], r[b][j]));
}
cout<<--res<<"\n";
}
}
/*
15 5 1
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
69200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
69296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
183 ms |
78760 KB |
Output is correct |
| 2 |
Correct |
136 ms |
79356 KB |
Output is correct |
| 3 |
Correct |
172 ms |
79428 KB |
Output is correct |
| 4 |
Correct |
202 ms |
79348 KB |
Output is correct |
| 5 |
Correct |
193 ms |
79332 KB |
Output is correct |
| 6 |
Correct |
220 ms |
79308 KB |
Output is correct |
| 7 |
Correct |
223 ms |
79252 KB |
Output is correct |
| 8 |
Correct |
97 ms |
79620 KB |
Output is correct |
| 9 |
Correct |
143 ms |
79872 KB |
Output is correct |
| 10 |
Correct |
170 ms |
79864 KB |
Output is correct |
| 11 |
Correct |
176 ms |
79864 KB |
Output is correct |
| 12 |
Correct |
169 ms |
79804 KB |
Output is correct |
| 13 |
Correct |
170 ms |
79820 KB |
Output is correct |
| 14 |
Correct |
181 ms |
79396 KB |
Output is correct |
| 15 |
Correct |
181 ms |
79248 KB |
Output is correct |
| 16 |
Correct |
189 ms |
79088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2076 ms |
77420 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
