This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
pair<int,int>maxi[25][100005];
int v[100005],st[100005];
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int n,k,q,i;
scanf("%d%d%d",&n,&k,&q);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
int u=0;
maxi[0][1].first=1;
for(i=1;i<=n;i++){
while(u && v[st[u]]<=v[i])
maxi[0][st[u]].second=i,u--;
st[++u]=i;
}
u=0;
maxi[0][n].second=n;
for(i=n;i>=1;i--){
while(u && v[st[u]]<=v[i])
maxi[0][st[u]].first=i,u--;
st[++u]=i;
}
int j;
for(i=1;i<20;i++){
for(j=1;j<=n;j++){
int x=maxi[i-1][j].first,y=maxi[i-1][j].second;
maxi[i][j]=make_pair(min(maxi[i-1][x].first,maxi[i-1][y].first),max(maxi[i-1][x].second,maxi[i-1][y].second));
}
}
for(i=1;i<=q;i++){
int l,r,ans=0;
scanf("%d%d",&l,&r);
if (l>r)
swap(l,r);
int x,y;
x=y=l;
int j;
for(j=19;j>=0;j--){
if (max(maxi[j][x].second,maxi[j][y].second)>=r)
continue;
int x2,y2;
x2=min(maxi[j][x].first,maxi[j][y].first);
y2=max(maxi[j][x].second,maxi[j][y].second);
x=x2;
y=y2;
ans=ans+(1<<j);
}
l=y;
x=y=r;
for(j=19;j>=0;j--){
if (min(maxi[j][x].first,maxi[j][y].first)<=l)
continue;
int x2,y2;
x2=min(maxi[j][x].first,maxi[j][y].first);
y2=max(maxi[j][x].second,maxi[j][y].second);
x=x2;
y=y2;
ans=ans+(1<<j);
}
printf("%d\n",ans);
}
return 0;
}
Compilation message (stderr)
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
10 | scanf("%d%d%d",&n,&k,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
12 | scanf("%d",&v[i]);
| ~~~~~^~~~~~~~~~~~
railway_trip.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
36 | scanf("%d%d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~
# | 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... |