#include <bits/stdc++.h>
using namespace std;
struct rmq {
const int L = 20;
vector<vector<int>> mn;
vector<vector<int>> mx;
vector<int> logs;
void build(vector<int> a) {
int n = (int) a.size();
mn.resize(L);
mx.resize(L);
mn[0] = a;
mx[0] = a;
logs.resize(n + 1);
for (int i = 2; i <= n; i++) {
logs[i] = logs[i >> 1] + 1;
}
for (int j = 1; j < L; j++) {
mn[j].resize(n);
mx[j].resize(n);
for (int i = 0; i + (1 << j) <= n; i++) {
mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
}
}
}
pair<int, int> query(int l, int r) {
int k = logs[r - l + 1];
int x = min(mn[l][k], mn[r - (1 << k) + 1][k]);
int y = max(mx[l][k], mx[r - (1 << k) + 1][k]);
return make_pair(x, y);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, q;
cin >> n >> k >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> prv(n);
vector<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[stk.back()] < a[i]) {
stk.pop_back();
}
prv[i] = (stk.empty() ? i : stk.back());
stk.push_back(i);
}
stk.clear();
vector<int> nxt(n);
for (int i = n - 1; i >= 0; i--) {
while (!stk.empty() && a[stk.back()] < a[i]) {
stk.pop_back();
}
nxt[i] = (stk.empty() ? i : stk.back());
stk.push_back(i);
}
vector<int> logs(n + 1);
for (int i = 2; i <= n; i++) {
logs[i] = logs[i >> 1] + 1;
}
const int LOG = 20;
vector<vector<int>> L(LOG, vector<int>(n));
vector<vector<int>> R(LOG, vector<int>(n));
L[0] = prv;
R[0] = nxt;
for (int j = 1; j < LOG; j++) {
rmq st;
st.build(L[j - 1]);
for (int i = 0; i < n; i++) {
L[j][i] = st.query(L[j - 1][i], R[j - 1][i]).first;
}
st.build(R[j - 1]);
for (int i = 0; i < n; i++) {
R[j][i] = st.query(L[j - 1][i], R[j - 1][i]).second;
}
}
vector<vector<vector<int>>> mn(LOG, vector<vector<int>>(n, vector<int>(LOG)));
vector<vector<vector<int>>> mx(LOG, vector<vector<int>>(n, vector<int>(LOG)));
for (int l = 0; l < LOG; l++) {
for (int i = 0; i < n; i++) {
mn[l][i][0] = L[l][i];
mx[l][i][0] = R[l][i];
}
for (int j = 1; j < LOG; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
mn[l][i][j] = min(mn[l][i][j - 1], mn[l][i + (1 << (j - 1))][j - 1]);
mx[l][i][j] = max(mx[l][i][j - 1], mx[l][i + (1 << (j - 1))][j - 1]);
}
}
}
auto QueryMin = [&](int i, int l, int r) {
int k = logs[r - l + 1];
return min(mn[i][l][k], mn[i][r - (1 << k) + 1][k]);
};
auto QueryMax = [&](int i, int l, int r) {
int k = logs[r - l + 1];
return max(mx[i][l][k], mx[i][r - (1 << k) + 1][k]);
};
cout << "! " << L[0][5] << " " << R[0][5] << '\n';
cout << QueryMin(1, 5, 5) << " " << QueryMax(1, 5, 5) << '\n';
while (q--) {
int a, b;
cin >> a >> b;
--a; --b;
if (a > b) {
swap(a, b);
}
int res = 0;
int from, to;
{
int l = a, r = a;
for (int i = LOG - 1; i >= 0; i--) {
if (QueryMin(i, l, r) <= b && b <= QueryMax(i, l, r)) {
continue;
}
int new_l = QueryMin(i, l, r);
int new_r = QueryMax(i, l, r);
l = new_l;
r = new_r;
res += (1 << i);
}
from = l;
to = r;
}
{
int l = b, r = b;
for (int i = LOG - 1; i >= 0; i--) {
if (max(from, QueryMin(i, l, r)) <= min(to, QueryMax(i, l, r))) {
continue;
}
int new_l = QueryMin(i, l, r);
int new_r = QueryMax(i, l, r);
l = new_l;
r = new_r;
//res += (1 << i);
}
}
cout << res << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1284 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
68812 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
68664 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
