#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
int N, K, Q, A[100005], stk[100005], stn, par[19][300005], dst[19][300005], dep[300005], L[100005], R[100005], idx[300005];
vector<int> edge[100005];
vector<pii> itv;
int lft(int x) { return 3 * x; }
int mid(int x) { return 3 * x + 1; }
int rht(int x) { return 3 * x + 2; }
void add_par(int x, int p, int a, int b, int i) {
idx[x] = i;
if (a < b) par[0][x] = lft(p);
else if (a > b) par[0][x] = rht(p);
else par[0][x] = mid(p);
dst[0][x] = min(a, b);
dep[x] = dep[par[0][x]] + 1;
for (int i = 1; i < 19; ++i) {
par[i][x] = par[i - 1][par[i - 1][x]];
dst[i][x] = dst[i - 1][x] + dst[i - 1][par[i - 1][x]];
}
}
int qry(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int ret = 0;
for (int i = 0; i < 19; ++i) if ((dep[x] - dep[y] >> i) & 1) {
ret += dst[i][x];
x = par[i][x];
}
for (int i = 18; i >= 0; --i) if (par[i][x] / 3 != par[i][y] / 3) {
ret += dst[i][x] + dst[i][y];
x = par[i][x], y = par[i][y];
}
if (idx[x] > idx[y]) swap(x, y);
int a = x % 3, b = y % 3;
int ret2 = ret + max(0, idx[y] - (b != 2) - idx[x] + (a == 0));
if (par[0][x] < 3) return ret2;
ret += dst[0][x] + dst[0][y];
x = par[0][x], y = par[0][y];
a = x % 3, b = y % 3;
if (a == 1 || b == 1 || a + b != 2) return min(ret, ret2);
return min(ret + 1, ret2);
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
itv.emplace_back(0, 1e9);
cin >> N >> K >> Q;
for (int i = 1; i <= N; ++i) cin >> A[i];
for (int i = 1; i <= N; ++i) {
while (stn && A[stk[stn - 1]] < A[i]) {
stn--;
itv.emplace_back(stk[stn], i - 1);
}
if (stn) itv.emplace_back(stk[stn - 1], i - 1);
if (stn && A[i] == A[stk[stn - 1]]) stn--;
stk[stn++] = i;
}
sort(itv.begin(), itv.end(), [&](pii a, pii b) {
if (a.ff == b.ff) return a.ss > b.ss;
return a.ff < b.ff;
});
stn = 0;
for (int i = 0; i < itv.size(); ++i) {
while (stn && itv[stk[stn - 1]].ss < itv[i].ff) --stn;
if (stn) edge[stk[stn - 1]].push_back(i);
stk[stn++] = i;
}
for (int i = 0; i < itv.size(); ++i) {
int c = edge[i].size(), k = 0;
for (auto j : edge[i]) {
++k;
int p = k - 1, q = c - k;
add_par(lft(j), i, p, q + 1, k);
add_par(mid(j), i, p, q, k);
add_par(rht(j), i, p + 1, q, k);
if (itv[j].ff == itv[j].ss) {
L[itv[j].ff] = lft(j);
R[itv[j].ff + 1] = rht(j);
}
}
}
while (Q--) {
int x, y; cin >> x >> y;
if (x > y) swap(x, y);
printf("%d\n", qry(L[x], R[y]) - 1);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3064 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3064 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3064 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3064 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 6 |
Correct |
7 ms |
3064 KB |
Output is correct |
| 7 |
Correct |
6 ms |
3064 KB |
Output is correct |
| 8 |
Correct |
6 ms |
3064 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3960 KB |
Output is correct |
| 2 |
Runtime error |
127 ms |
111080 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
134 ms |
111720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
22120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
