#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e5+10;
int a[maxn], l[maxn][2], r[maxn][2];
// l[] e r[] salvam tanto o primeiro elemento maior como a distância
vector<int> pos[21];
int dist(int x, int y, int k) {
// se x==y ele retorna -1 e é pra retornar isso mesmo
if(x > y) swap(x, y);
return lower_bound(pos[k].begin(), pos[k].end(), y) - lower_bound(pos[k].begin(), pos[k].end(), x) - 1;
}
int main() {
int n, k, q; scanf("%d %d %d", &n, &k, &q);
for(int i = 0; i < n; i++) {
scanf("%d", a+i);
for(int j = 0; j <= a[i]; j++)
pos[j].push_back(i);
}
for(int i = 0; i < n; i++) {
if(a[i] == k) { l[i][0] = i; l[i][1] = 0; continue; }
l[i][0] = i-1; l[i][1] = 1;
while(a[l[i][0]] <= a[i]) {
l[i][1] = (a[l[i][0]] == a[i] ? l[l[i][0]][1] : 0) + 1;
l[i][0] = l[l[i][0]][0];
}
}
for(int i = n-1; i >= 0; i--) {
if(a[i] == k) { r[i][0] = i, r[i][1] = 0; continue; }
r[i][0] = i+1; r[i][1] = 1;
while(a[r[i][0]] <= a[i]) {
r[i][1] = (a[r[i][0]] == a[i] ? r[r[i][0]][1] : 0) + 1;
r[i][0] = r[r[i][0]][0];
}
}
while(q--) {
int x, y; scanf("%d %d", &x, &y);
--x, --y;
pair<int,int> L[2], R[2]; // pair(elemento, distancia)
L[0] = R[0] = {x, 0}; L[1] = R[1] = {y, 0};
int ans = 0x3f3f3f3f;
auto upd = [&](int k) {
L[k].second += l[L[k].first][1];
L[k].first = l[L[k].first][0];
R[k].second += r[R[k].first][1];
R[k].first = r[R[k].first][0];
R[k].second = min(R[k].second, L[k].second+1);
L[k].second = min(L[k].second, R[k].second+1);
};
auto get_ans = [&]() {
ans = min(ans, L[0].second + L[1].second + dist(L[0].first, L[1].first, min(a[L[0].first], a[L[1].first])));
ans = min(ans, R[0].second + L[1].second + dist(R[0].first, L[1].first, min(a[R[0].first], a[L[1].first])));
ans = min(ans, L[0].second + R[1].second + dist(L[0].first, R[1].first, min(a[L[0].first], a[R[1].first])));
ans = min(ans, R[0].second + R[1].second + dist(R[0].first, R[1].first, min(a[R[0].first], a[R[1].first])));
};
L[0] = R[0] = {x, 0};
for(int i = 0; i < k; i++) {
L[1] = R[1] = {y, 0};
for(int j = 0; j < k; j++) {
get_ans();
upd(1);
}
upd(0);
}
printf("%d\n", ans);
}
}
Compilation message
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:19:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | int n, k, q; scanf("%d %d %d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
railway_trip.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | int x, y; scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
84 ms |
6404 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2076 ms |
7052 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
8020 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
