이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define X first
#define Y second
const int N = 1e5 + 1;
int lef[N][20];
int rig[N][20];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int k; cin >> k;
int q; cin >> q;
vector<int> a(n);
for(int&x : a) cin >> x;
auto build = [&](bool inv) {
stack<int> st;
for(int i = 0 ; i < n ; ++i) {
while (st.size() && a[st.top()] < a[i])
st.pop();
if (st.size()) {
int u = st.top();
if (inv) rig[n - i][0] = n - u;
else lef[i + 1][0] = u + 1;
}
st.push(i);
}
reverse(a.begin(),a.end());
};
build(0);
build(1); rig[n][0] = n;
for(int i = 0 ; i < 16 ; ++i)
for(int j = 1 ; j <= n ; ++j) {
int x = lef[j][i];
int y = rig[j][i];
lef[j][i + 1] = min(lef[x][i],lef[y][i]);
rig[j][i + 1] = max(rig[x][i],rig[y][i]);
}
for(int i = 0 ; i < q ; ++i) {
int x; cin >> x;
int y; cin >> y;
if (x > y) x ^= (y ^= (x ^= y));
int ans = 0;
int l = x;
int r = x;
for(int j = 16 ; j >= 0 ; --j) if (max(rig[l][j],rig[r][j]) < y) {
ans += (1 << j);
int pl = min(lef[l][j],lef[r][j]);
int pr = max(rig[l][j],rig[r][j]);
l = pl;
r = pr;
}
x = r;
l = y;
r = y;
for(int j = 16 ; j >= 0 ; --j) if (min(lef[l][j],lef[r][j]) > x) {
ans += (1 << j);
int pl = min(lef[l][j],lef[r][j]);
int pr = max(rig[l][j],rig[r][j]);
l = pl;
r = pr;
}
cout << ans << "\n";
}
}
/*
9 3 3
3 1 1 1 2 2 2 3 3
2 4
4 9
6 7
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |