#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;
const int INF = 0x3f3f3f3f;
template<class T>
class Vector: public vector<T> {
public:
Vector(): vector<T>() {}
Vector(int n): vector<T>(n) {}
Vector(int n, const T& e): vector<T>(n, e){}
T& operator[](size_t pos) {
assert(0 <= pos && pos < vector<T>::size());
return vector<T>::operator[](pos);
}
const T& operator[](size_t pos) const {
assert(0 <= pos && pos < vector<T>::size());
return vector<T>::operator[](pos);
}
};
int main() {
#ifdef LOCAL_RUN
freopen("task.in", "r", stdin);
freopen("task.out", "w", stdout);
//freopen("task.err", "w", stderr);
#endif // ONLINE_JUDGE
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, q;
cin >> n >> k >> q;
Vector<int> A(n);
Vector<int> stk;
Vector<Vector<int>> graph(n);
for (int i = 0; i < n; ++i) {
cin >> A[i];
int prev = -1;
while (!stk.empty() && A[i] > A[stk.back()]) {
if (A[stk.back()] > prev) {
graph[i].push_back(stk.back());
graph[stk.back()].push_back(i);
}
prev = A[stk.back()];
stk.pop_back();
}
if (!stk.empty()) {
graph[i].push_back(stk.back());
graph[stk.back()].push_back(i);
}
stk.push_back(i);
}
if (k <= 20 && q > 50) {
Vector<Vector<int>> dists(n, Vector<int>(k + 1, INF));
Vector<Vector<int>> n1(n, Vector<int>(k + 1, -1));
Vector<Vector<int>> n2(n, Vector<int>(k + 1, -1));
for (int i = 0; i < n; ++i) {
n1[i][A[i]] = i;
dists[i][A[i]] = 0;
queue<pair<int, int>> q;
q.push(make_pair(i, 0));
while (!q.empty()) {
int node = q.front().first;
int cost = q.front().second;
q.pop();
for (int to: graph[node]) {
if (A[to] > A[node] && dists[i][A[to]] >= cost + 1) {
dists[i][A[to]] = cost + 1;
q.push(make_pair(to, cost + 1));
if (n1[i][A[to]] == -1) {
n1[i][A[to]] = to;
} else {
n2[i][A[to]] = to;
}
}
}
}
}
Vector<int> log2(n + 1, 0);
for (int i = 2; i <= n; ++i) {
log2[i] = log2[i / 2] + 1;
}
int clog2 = log2[n];
Vector<Vector<int>> rmq(clog2 + 1, Vector<int>(n));
for (int i = 0; i < n; ++i) {
rmq[0][i] = A[i];
}
for (int j = 1; j <= clog2; ++j) {
int y = 1 << j - 1;
for (int i = 0; i + (1 << j) <= n; ++i) {
rmq[j][i] = max(rmq[j - 1][i], rmq[j - 1][i + y]);
}
}
auto getMax = [&](int left, int right) -> int {
if (right < left) {
return -INF;
}
int d = log2[right - left + 1];
return max(rmq[d][left], rmq[d][right - (1 << d) + 1]);
};
Vector<int> valCnt(k + 1, 0);
Vector<int> posInVal(n);
for (int i = 0; i < n; ++i) {
posInVal[i] = valCnt[A[i]]++;
}
while (q-- > 0) {
int from, to;
cin >> from >> to;
from--; to--;
int h = max(A[from], A[to]);
int ans = INF;
for (int i = h; i <= k; ++i) {
for (int x1: {n1[from][i], n2[from][i]}) {
for (int x2: {n1[to][i], n2[to][i]}) {
int p1 = min(x1, x2);
int p2 = max(x1, x2);
if (x1 != -1 && x2 != -1 &&
getMax(p1 + 1, p2 - 1) <= A[x1]) {
int cost = dists[from][i] + dists[to][i];
cost += posInVal[p2] - posInVal[p1] - 1;
ans = min(ans, cost);
}
}
}
}
cout << ans << '\n';
}
} else {
while (q-- > 0) {
int s, d;
cin >> s >> d;
s--; d--;
Vector<int> dist(n, -1);
dist[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty() && dist[d] == -1) {
int node = q.front();
q.pop();
for (int to: graph[node]) {
if (dist[to] == -1) {
dist[to] = dist[node] + 1;
q.push(to);
}
}
}
cout << dist[d] - 1 << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2188 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2188 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2188 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2188 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2188 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2188 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2188 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2188 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2188 KB |
Output is correct |
| 2 |
Correct |
123 ms |
8900 KB |
Output is correct |
| 3 |
Correct |
113 ms |
8976 KB |
Output is correct |
| 4 |
Correct |
149 ms |
9048 KB |
Output is correct |
| 5 |
Correct |
139 ms |
9080 KB |
Output is correct |
| 6 |
Correct |
146 ms |
9124 KB |
Output is correct |
| 7 |
Correct |
126 ms |
9144 KB |
Output is correct |
| 8 |
Correct |
49 ms |
8988 KB |
Output is correct |
| 9 |
Correct |
59 ms |
8732 KB |
Output is correct |
| 10 |
Correct |
49 ms |
8988 KB |
Output is correct |
| 11 |
Correct |
123 ms |
8884 KB |
Output is correct |
| 12 |
Correct |
116 ms |
8888 KB |
Output is correct |
| 13 |
Correct |
126 ms |
8888 KB |
Output is correct |
| 14 |
Correct |
119 ms |
8884 KB |
Output is correct |
| 15 |
Correct |
119 ms |
8888 KB |
Output is correct |
| 16 |
Correct |
116 ms |
8888 KB |
Output is correct |
| 17 |
Correct |
153 ms |
9144 KB |
Output is correct |
| 18 |
Correct |
123 ms |
9144 KB |
Output is correct |
| 19 |
Correct |
83 ms |
9144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
103 ms |
46448 KB |
Execution killed because of forbidden syscall writev (20) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
9144 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
