#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
using ll = long long;
int const nmax = 100000;
int const lgmax = 20;
int rmq[1 + lgmax][1 + nmax], rmq2[1 + lgmax][1 + nmax];
int v[5 + nmax];
void computeRmq(int n) {
for(int i = 1;i <= n; i++)
rmq[0][i] = i;
auto bestOf = [&](int x, int y) {
if(v[x] <= v[y])
return y;
else
return x;
};
for(int h = 1; h <= lgmax; h++)
for(int i = 1; i <= n - (1 << h) + 1; i++)
rmq[h][i] = bestOf(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
}
void computeRmq2(int n) {
for(int i = 1;i <= n; i++)
rmq2[0][i] = i;
auto bestOf = [&](int x, int y) {
if(v[x] < v[y])
return y;
else
return x;
};
for(int h = 1; h <= lgmax; h++)
for(int i = 1; i <= n - (1 << h) + 1; i++)
rmq2[h][i] = bestOf(rmq2[h - 1][i], rmq2[h - 1][i + (1 << (h - 1))]);
}
int extract(int x, int y) {
if(y < x)
return 0;
auto lg = [&](int n) {
return 31 - __builtin_clz(n);
};
int h = lg(y - x + 1);
auto bestOf = [&](int x, int y) {
if(v[x] <= v[y])
return y;
else
return x;
};
return bestOf(rmq[h][x], rmq[h][y - (1 << h) + 1]);
}
int extract2(int x, int y) {
if(y < x)
return 0;
auto lg = [&](int n) {
return 31 - __builtin_clz(n);
};
int h = lg(y - x + 1);
auto bestOf = [&](int x, int y) {
if(v[x] < v[y])
return y;
else
return x;
};
return bestOf(rmq2[h][x], rmq2[h][y - (1 << h) + 1]);
}
std::vector<int> tree[5 + nmax], g[5 + nmax];
std::vector<int> spec[5 + nmax];
void addEdge(int x, int y) {
if(0 < x && 0 < y) {
g[x].push_back(y);
g[y].push_back(x);
}
}
void addTreeEdge(int x, int y) {
if(0 < x && 0 < y) {
//std::cout << "Tree: " << x << " " << y << '\n';
tree[x].push_back(y);
tree[y].push_back(x);
}
}
void addSpec(int x, int y) {
if(0 < x && 0 < y) {
spec[x].push_back(y);
}
}
void buildTree(int from, int to, int left, int right, int father) {
if(from <= to) {
int node;
if(left == father)
node = extract2(from, to);
else
node = extract(from, to);
if(0 < left && v[extract(left + 1, node - 1)] != v[node]) {
addEdge(left, node);
addSpec(node, left);
}
if(0 < right && v[extract(node + 1, right - 1)] != v[node]) {
addEdge(right, node);
addSpec(node, right);
}
addTreeEdge(father, node);
buildTree(from, node - 1, left, node, node);
buildTree(node + 1, to, node, right, node);
}
}
int seen[5 + nmax], sz[5 + nmax];
int level[5 + nmax], touched[5 + nmax];
int timestamp = 0;
void computesz(int node, int parent) {
sz[node] = 1;
touched[node] = timestamp;
for(int h = 0; h < tree[node].size(); h++) {
int to = tree[node][h];
if(to != parent && seen[to] == 0) {
computesz(to, node);
sz[node] += sz[to];
}
}
}
int getCentroid(int node, int parent, int target) {
for(int h = 0; h < tree[node].size(); h++) {
int to = tree[node][h];
if(parent != to && seen[to] == 0 && target <= sz[to])
return getCentroid(to, node, target);
}
return node;
}
int dist[1 + lgmax * 3][5 + nmax], fromWho[1 + lgmax * 3][5 + nmax];
void computeDist(int start, int level) {
if(touched[start] != timestamp)
return ;
std::queue<int> q;
q.push(start);
dist[level][start] = 0;
while(0 < q.size()) {
int node = q.front();
fromWho[level][node] = start;
q.pop();
for(int h = 0; h < g[node].size(); h++) {
int to = g[node][h];
if(touched[to] == timestamp && dist[level][node] + 1 < dist[level][to]) {
dist[level][to] = dist[level][node] + 1;
q.push(to);
}
}
}
}
void solve(int root, int level) {
++timestamp;
computesz(root, 0);
int centroid = getCentroid(root, 0, sz[root] / 2);
computeDist(centroid, level++);
for(int h = 0; h < spec[centroid].size(); h++) {
computeDist(spec[centroid][h], level++);
}
assert(level <= lgmax * 3);
seen[centroid] = 1;
for(int h = 0; h < tree[centroid].size(); h++) {
int to = tree[centroid][h];
if(seen[to] == 0)
solve(to, level);
}
}
void resetDist(int n) {
for(int i = 0; i <= lgmax * 3; i++)
for(int j = 1; j <= n; j++)
dist[i][j] = nmax * 2;
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n, k, q;
std::cin >> n >> k >> q;
for(int i = 1; i <= n; i++)
std::cin >> v[i];
computeRmq(n);
computeRmq2(n);
buildTree(1, n, 0, 0, 0);
resetDist(n);
solve(1, 0);
for(int i = 1; i <= q; i++) {
int x, y;
std::cin >> x >> y;
int result = nmax * 2;
for(int h = 0; h <= lgmax * 3; h++) {
if(fromWho[h][x] == fromWho[h][y])
result = std::min(result, dist[h][x] + dist[h][y] - 1);
}
std::cout << result << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7892 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7880 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7892 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
7892 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
443 ms |
70884 KB |
Output is correct |
| 2 |
Correct |
434 ms |
71016 KB |
Output is correct |
| 3 |
Incorrect |
436 ms |
72288 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
446 ms |
71760 KB |
Output is correct |
| 2 |
Incorrect |
463 ms |
73596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
