#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = (int)1e5;
const int MAXLOG = (int)17;
int a[N+2] , b[N+2] ,l[N+2];
int lef[N+2][MAXLOG+2] , rig[N+2][MAXLOG+2];
int n,k,q;
void process(int l,int r){
if (l>r) swap(l,r);
int ans = 0;
int t_l , t_r;
t_l = t_r = l;
for(int j = MAXLOG; j >= 0; --j){
int nxt_r = max(rig[t_l][j] , rig[t_r][j]);
int nxt_l = min(lef[t_l][j] , lef[t_r][j]);
if (nxt_r < r){
t_r = nxt_r , t_l = nxt_l;
ans += (1<<j);
}
}
l = t_r;
// cout<<l<<' '<<ans<<'\n';
t_l = t_r = r;
for(int j = MAXLOG; j >= 0; --j){
int nxt_r = max(rig[t_l][j] , rig[t_r][j]);
int nxt_l = min(lef[t_l][j] , lef[t_r][j]);
if (nxt_l > l){
t_r = nxt_r , t_l = nxt_l;
ans += (1<<j);
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
}
cin>>n>>k>>q;
for(int i = 1; i <= n; ++i) cin>>l[i];
for(int i = 1; i <= q; ++i) cin>>a[i]>>b[i];
vector<int>st;
for(int i = 1; i <= n; ++i) {
while (st.size() && l[st.back()] < l[i]) st.pop_back();
if (st.size()) lef[i][0] = st.back(); else lef[i][0] = i;
st.push_back(i);
}
st.clear();
for(int i = n; i >= 1; --i) {
while (st.size() && l[st.back()] < l[i]) st.pop_back();
if (st.size()) rig[i][0] = st.back(); else rig[i][0] = i;
st.push_back(i);
}
// for(int i = 1; i <= n; ++i) cout<<i<<' '<<lef[i][0]<<' '<<rig[i][0]<<'\n';
for(int j = 1; j <= MAXLOG; ++j) {
for(int i = 1; i <= n; ++i) {
int l = min(lef[lef[i][j-1]][j-1],lef[rig[i][j-1]][j-1]);
int r = max(rig[lef[i][j-1]][j-1],rig[rig[i][j-1]][j-1]);
lef[i][j] = l , rig[i][j] = r;
}
}
for(int i = 1; i <= q; ++i) process(a[i] , b[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:43:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |