#include <bits/stdc++.h>
using namespace std;
struct kek {
int mx, l, r;
};
const int N = 1e5 + 7;
const int L = 19;
int n, k, q;
int a[N], pos[N];
int nxt[N];
int prv[N];
kek go[L][N];
kek merge(const kek &a, const kek &b) {
if (a.mx == b.mx) {
return {a.mx, min(a.l, b.l), max(a.r, b.r)};
}
return a.mx > b.mx ? a : b;
}
kek t[2 * N];
kek get(int l, int r) {
kek ret = {-1, -1, -1};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
ret = merge(ret, t[l]);
++l;
}
if (r & 1) {
--r;
ret = merge(ret, t[r]);
}
}
return ret;
}
int dist(int i, int j) {
if (i < j) {
if (nxt[i] == j) {
return 1;
}
kek lol = {a[i], i, i};
int ret = 2;
for (int p = L - 1; p >= 0; --p) {
kek lol1 = merge(go[p][lol.l], go[p][lol.r]);
bool ok = false;
if (lol1.mx >= a[j]) {
ok = true;
} else {
if (nxt[lol1.r] == j) {
ok = true;
}
}
if (!ok) {
ret += (1 << p);
lol = lol1;
}
}
return ret;
}
if (prv[i] == j) {
return 1;
}
kek lol = {a[i], i, i};
int ret = 2;
for (int p = L - 1; p >= 0; --p) {
kek lol1 = merge(go[p][lol.l], go[p][lol.r]);
bool ok = false;
if (lol1.mx >= a[j]) {
ok = true;
} else {
if (prv[lol1.l] == j) {
ok = true;
}
}
if (!ok) {
ret += (1 << p);
lol = lol1;
}
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> q;
for (int i = 0; i < n; ++i) {
cin >> a[i];
--a[i];
}
for (int i = 0; i < n; ++i) {
nxt[i] = n;
prv[i] = -1;
}
{
vector<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.back()] <= a[i]) {
nxt[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
}
{
vector<int> st;
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && a[st.back()] <= a[i]) {
prv[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
}
{
vector<int> cnt(k, 0);
for (int i = 0; i < n; ++i) {
pos[i] = cnt[a[i]];
++cnt[a[i]];
}
}
for (int i = 0; i < n; ++i) {
t[i + n] = {a[i], i, i};
}
for (int i = n - 1; i > 0; --i) {
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
for (int i = 0; i < n; ++i) {
go[0][i] = {a[i], i, i};
if (prv[i] != -1) {
go[0][i] = merge(go[0][i], {a[prv[i]], prv[i], prv[i]});
}
if (nxt[i] != n) {
go[0][i] = merge(go[0][i], {a[nxt[i]], nxt[i], nxt[i]});
}
}
for (int p = 1; p < L; ++p) {
for (int i = 0; i < n; ++i) {
go[p][i] = go[p - 1][i];
go[p][i] = merge(go[p][i], go[p - 1][go[p - 1][i].l]);
go[p][i] = merge(go[p][i], go[p - 1][go[p - 1][i].r]);
}
}
while (q--) {
int l, r;
cin >> l >> r;
--l;
--r;
if (l > r) {
swap(l, r);
}
auto lol = get(l + 1, r);
if (lol.mx < min(a[l], a[r])) {
cout << "0\n";
continue;
}
if (lol.mx < a[l]) {
cout << dist(r, l) - 1 << "\n";
continue;
}
if (lol.mx < a[r]) {
cout << dist(l, r) - 1 << "\n";
continue;
}
cout << dist(l, lol.l) + dist(r, lol.r) + pos[lol.r] - pos[lol.l] - 1 << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
26884 KB |
Output is correct |
| 2 |
Incorrect |
183 ms |
26980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
216 ms |
26764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
