| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 24768 | Ushio | Railway Trip (JOI17_railway_trip) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;
class SegmentTree {
public:
SegmentTree() = default;
SegmentTree(const vector<int>& a):
tree(vector<pair<int, int>>(4 * SZ(a) + 5)), n(SZ(a)) {
build(0, 0, n - 1, a);
}
pair<int, int> query(int left, int right) const {
pair<int, int> ret = query(0, 0, n - 1, left, right);
ret.second = -ret.second;
return ret;
}
private:
vector<pair<int, int>> tree;
int n;
void build(int node, int left, int right, const vector<int>& a) {
if (left == right) {
tree[node] = make_pair(a[left], -left);
} else {
int mid = (left + right) / 2;
build(2 * node + 1, left, mid, a);
build(2 * node + 2, mid + 1, right, a);
tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
}
}
pair<int, int> query(int node, int left, int right, int lq, int rq) const {
if (lq <= left && right <= rq) {
return tree[node];
} else {
int mid = (left + right) / 2;
pair<int, int> ret(-1, -1);
if (lq <= mid) {
ret = query(2 * node + 1, left, mid, lq, rq);
}
if (rq > mid) {
ret = max(ret, query(2 * node + 2, mid + 1, right, lq, rq));
}
return ret;
}
}
};
vector<vector<int>> tree;
vector<int> indexToNode;
SegmentTree t;
const int LOG = 21;
array<vector<int>, LOG> anc;
array<vector<int>, LOG> ancCost;
vector<int> depth;
vector<int> posInParent;
int build(const vector<int>& a, int left, int right) {
tree.push_back(vector<int>());
int index = SZ(tree) - 1;
if (left + 1 == right) {
indexToNode[left] = index;
} else {
pair<int, int> imax = t.query(left + 1, right - 1);
vector<int> poss = {left, imax.second};
while (imax.second + 1 < right) {
pair<int, int> cmax = t.query(imax.second + 1, right - 1);
if (cmax.first != imax.first) {
break;
}
poss.push_back(cmax.second);
imax = cmax;
}
poss.push_back(right);
for (int i = 0; i < SZ(poss) - 1; ++i) {
int x = build(a, poss[i], poss[i + 1]);
tree[index].push_back(x);
}
}
return index;
}
void assignParent(int son, int parent, int costLeft, int costRight) {
costLeft = min(costLeft, costRight + 1);
costRight = min(costRight, costLeft + 1);
if (costLeft == costRight + 1) {
anc[0][son] = 3 * parent;
ancCost[0][son] = costRight;
} else if (costLeft == costRight) {
anc[0][son] = 3 * parent + 1;
ancCost[0][son] = costRight;
} else {
anc[0][son] = 3 * parent + 2;
ancCost[0][son] = costLeft;
}
}
void genDistTrees(int node) {
for (int i = 0; i < SZ(tree[node]); ++i) {
int to = tree[node][i];
int costLeft = i;
int costRight = SZ(tree[node]) - i - 1;
posInParent[to] = i;
depth[to] = depth[node] + 1;
assignParent(3 * to, node, costLeft + 1, costRight);
assignParent(3 * to + 1, node, costLeft, costRight);
assignParent(3 * to + 2, node, costLeft, costRight + 1);
genDistTrees(to);
}
}
pair<int, int> ascend(int node, int height) {
int cost = 0;
for (int k = 0; k < LOG; ++k) {
if (height & (1 << k)) {
cost += ancCost[k][node];
node = anc[k][node];
}
}
return make_pair(node, cost);
}
void solve() {
int n, k, q;
cin >> n >> k >> q;
vector<int> a(n);
int rootCycle = true;
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (i != 0 && i != n - 1 && a[i] == k) {
rootCycle = false;
}
}
t = SegmentTree(a);
indexToNode = vector<int>(n);
tree.reserve(2 * n);
int root = build(a, 0, n - 1);
for (int i = 0; i < LOG; ++i) {
anc[i] = vector<int>(3 * SZ(tree));
ancCost[i] = vector<int>(3 * SZ(tree));
}
for (int i = 0; i < 3; ++i) {
anc[i][root + i] = root;
ancCost[i][root + i] = 0;
}
depth = vector<int>(SZ(tree), 0);
posInParent = vector<int>(SZ(tree), -1);
genDistTrees(root);
for (int k = 1; k < LOG; ++k) {
for (int i = 0; i < SZ(anc[k]); ++i) {
anc[k][i] = anc[k - 1][anc[k - 1][i]];
ancCost[k][i] = ancCost[k - 1][i] +
ancCost[k - 1][anc[k - 1][i]];
}
}
while (q-- > 0) {
int a, b;
cin >> a >> b;
a--; b--;
if (a > b) {
swap(a, b);
}
if (a + 1 == b) {
cout << "0\n";
continue;
}
a = indexToNode[a] * 3 + 2;
b = indexToNode[b - 1] * 3;
int add = 0;
if (depth[b / 3] > depth[a / 3]) {
pair<int, int> c = ascend(b, depth[b / 3] - depth[a / 3]);
b = c.first;
add += c.second;
} else if (depth[a / 3] > depth[b / 3]) {
pair<int, int> c = ascend(a, depth[a / 3] - depth[b / 3]);
a = c.first;
add += c.second;
}
for (int k = LOG - 1; k >= 0; --k) {
if (anc[k][a] / 3 != anc[k][b] / 3) {
add += ancCost[k][a] + ancCost[k][b];
a = anc[k][a];
b = anc[k][b];
}
}
int ans = add + posInParent[b / 3] - posInParent[a / 3] - 1
+ (a % 3 == 2) + (b % 3 == 0);
if (anc[0][a] / 3 != root || rootCycle) {
ans = min(ans, add + posInParent[a / 3] +
(SZ(tree[anc[0][a] / 3]) - posInParent[b / 3] - 1) +
(a % 3 == 0) + (b % 3 == 2) + 1);
}
cout << ans - 1 << '\n';
}
}
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);
thread solver(solve);
solver.join();
}