#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;
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<int> leftEq(n, -1), leftLt(n, -1);
Vector<int> rightEq(n, -1), rightLt(n, -1);
for (int i = 0; i < n; ++i) {
cin >> A[i];
while (!stk.empty() && A[i] >= A[stk.back()]) {
leftEq[i] = stk.back();
if (A[i] > A[stk.back()]) {
leftLt[i] = stk.back();
}
stk.pop_back();
}
stk.push_back(i);
}
stk.clear();
stk.clear();
for (int i = n - 1; i >= 0; --i) {
while (!stk.empty() && A[i] >= A[stk.back()]) {
rightEq[i] = stk.back();
if (A[i] > A[stk.back()]) {
rightLt[i] = stk.back();
}
stk.pop_back();
}
stk.push_back(i);
}
Vector<int> leftSon(n, -1), rightSon(n, -1);
Vector<int> parent(n, -1);
Vector<int> skip(n, -1);
Vector<int> level(n, 0);
queue<pair<int, int>> qu;
qu.push(make_pair(1, 0));
while (!qu.empty()) {
int sonType = qu.front().first;
int node = qu.front().second;
qu.pop();
if (sonType == 0) {
leftSon[node] = leftEq[node];
rightSon[node] = rightLt[node];
} else {
leftSon[node] = leftLt[node];
rightSon[node] = rightEq[node];
}
if (leftSon[node] != -1) {
qu.push(make_pair(0, leftSon[node]));
parent[leftSon[node]] = node;
level[leftSon[node]] = level[node] + 1;
}
if (rightSon[node] != -1) {
qu.push(make_pair(1, rightSon[node]));
parent[rightSon[node]] = node;
level[rightSon[node]] = level[node] + 1;
}
}
for (int node = 0; node < n; ++node) {
for (int des = leftSon[node]; des != -1; des = rightSon[des]) {
if (des != leftSon[node] &&
(rightSon[des] == -1 || A[des] > A[rightSon[des]])) {
skip[des] = node;
}
}
for (int des = rightSon[node]; des != -1; des = leftSon[des]) {
if (des != rightSon[node] &&
(leftSon[des] == -1 || A[des] > A[leftSon[des]])) {
skip[des] = node;
}
}
}
const int LOG = 20;
array<Vector<int>, LOG> anc;
fill(anc.begin(), anc.end(), Vector<int>(n));
parent[0] = 0;
for (int node = 0; node < n; ++node) {
anc[0][node] = parent[node];
}
for (int k = 1; k < LOG; ++k) {
for (int node = 0; node < n; ++node) {
anc[k][node] = anc[k - 1][anc[k - 1][node]];
}
}
array<Vector<int>, LOG> skipAnc;
array<Vector<int>, LOG> skipCost;
fill(skipAnc.begin(), skipAnc.end(), Vector<int>(n));
fill(skipCost.begin(), skipCost.end(), Vector<int>(n));
for (int node = 0; node < n; ++node) {
if (skip[node] == -1) {
skip[node] = parent[node];
}
skipAnc[0][node] = skip[node];
skipCost[0][node] = (skip[node] != node);
}
for (int k = 1; k < LOG; ++k) {
for (int node = 0; node < n; ++node) {
skipAnc[k][node] = skipAnc[k - 1][skipAnc[k - 1][node]];
skipCost[k][node] = skipCost[k - 1][node]
+ skipCost[k - 1][skipAnc[k - 1][node]];
}
}
auto goUp = [&](int node, int lvl) -> int {
for (int k = 0; k < LOG; ++k) {
if (lvl & (1 << k)) {
node = anc[k][node];
}
}
return node;
};
auto lca = [&](int x, int y) -> int {
if (level[y] > level[x]) {
y = goUp(y, level[y] - level[x]);
} else if (level[x] > level[y]) {
x = goUp(x, level[x] - level[y]);
}
if (x == y) {
return x;
}
for (int k = LOG - 1; k >= 0; --k) {
if (anc[k][x] != anc[k][y]) {
x = anc[k][x];
y = anc[k][y];
}
}
return parent[x];
};
while (q-- > 0) {
int x, y;
cin >> x >> y;
x--; y--;
int l = lca(x, y);
int ans = 0;
for (int k = LOG - 1; k >= 0; --k) {
if (level[skipAnc[k][x]] >= level[l]) {
ans += skipCost[k][x];
x = skipAnc[k][x];
}
if (level[skipAnc[k][y]] >= level[l]) {
ans += skipCost[k][y];
y = skipAnc[k][y];
}
}
int ans1 = ans + level[x] + level[y] - 2 * level[l];
int v1 = skip[x];
int v2 = skip[y];
if (level[v1] > level[v2]) {
swap(v1, v2);
swap(x, y);
}
int ans2 = ans + 1 + level[x] - level[v2];
int ans3 = ans + 2;
for (int k = LOG - 1; k >= 0; --k) {
if (level[skipAnc[k][v2]] >= level[v1]) {
ans3 += skipCost[k][v2];
v2 = skipAnc[k][v2];
}
}
ans3 += level[v2] - level[v1];
ans = min({ans1, ans2, ans3});
cout << ans - 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 |
Incorrect |
0 ms |
2188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2452 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
29996 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
29996 KB |
Execution killed because of forbidden syscall writev (20) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
30044 KB |
Execution killed because of forbidden syscall writev (20) |
| 2 |
Halted |
0 ms |
0 KB |
- |
