#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N=100050;
const int L=18;
int a[N],S[N],c,mx[N][L],mn[N][L],n,k,q,s,t,m,l,r;
int main()
{
scanf("%i %i %i",&n,&k,&q);
for(int i=1;i<=n;i++) scanf("%i",&a[i]);
for(int i=1;i<=n;i++){ while(c && a[S[c]]<a[i]) c--;mn[i][0]=c?S[c]:i;S[++c]=i;}c=0;
for(int i=n;i>=1;i--){ while(c && a[S[c]]<a[i]) c--;mx[i][0]=c?S[c]:i;S[++c]=i;}c=0;
for(int j=1;j<L;j++) for(int i=1;i<=n;i++)
{
mn[i][j]=min(mn[mn[i][j-1]][j-1],mn[mx[i][j-1]][j-1]);
mx[i][j]=max(mx[mn[i][j-1]][j-1],mx[mx[i][j-1]][j-1]);
}
while(q--)
{
scanf("%i %i",&s,&t);
if(s>t) swap(s,t);
int ans=0;
l=r=s;
for(int j=L-1;~j;j--) if(max(mx[l][j],mx[r][j])<t)
{
ans+=1<<j;
tie(l,r)=mp(min(mn[l][j],mn[r][j]),max(mx[l][j],mx[r][j]));
}
m=r;l=r=t;
for(int j=L-1;~j;j--) if(min(mn[l][j],mn[r][j])>m)
{
ans+=1<<j;
tie(l,r)=mp(min(mn[l][j],mn[r][j]),max(mx[l][j],mx[r][j]));
}
printf("%i\n",ans);
}
return 0;
}
Compilation message
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i",&n,&k,&q);
~~~~~^~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:10:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%i",&a[i]);
~~~~~^~~~~~~~~~~~
railway_trip.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&s,&t);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
3 ms |
384 KB |
Output is correct |
| 9 |
Correct |
3 ms |
404 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
53 ms |
15096 KB |
Output is correct |
| 3 |
Correct |
73 ms |
15224 KB |
Output is correct |
| 4 |
Correct |
63 ms |
15104 KB |
Output is correct |
| 5 |
Correct |
69 ms |
15188 KB |
Output is correct |
| 6 |
Correct |
73 ms |
15224 KB |
Output is correct |
| 7 |
Correct |
63 ms |
15352 KB |
Output is correct |
| 8 |
Correct |
65 ms |
15480 KB |
Output is correct |
| 9 |
Correct |
73 ms |
15616 KB |
Output is correct |
| 10 |
Correct |
69 ms |
15480 KB |
Output is correct |
| 11 |
Correct |
66 ms |
15480 KB |
Output is correct |
| 12 |
Correct |
63 ms |
15736 KB |
Output is correct |
| 13 |
Correct |
74 ms |
15608 KB |
Output is correct |
| 14 |
Correct |
74 ms |
15480 KB |
Output is correct |
| 15 |
Correct |
75 ms |
15608 KB |
Output is correct |
| 16 |
Correct |
93 ms |
15480 KB |
Output is correct |
| 17 |
Correct |
69 ms |
15480 KB |
Output is correct |
| 18 |
Correct |
66 ms |
15608 KB |
Output is correct |
| 19 |
Correct |
44 ms |
15480 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
201 ms |
15384 KB |
Output is correct |
| 2 |
Correct |
243 ms |
16888 KB |
Output is correct |
| 3 |
Correct |
201 ms |
16724 KB |
Output is correct |
| 4 |
Correct |
200 ms |
16860 KB |
Output is correct |
| 5 |
Correct |
185 ms |
16760 KB |
Output is correct |
| 6 |
Correct |
181 ms |
16732 KB |
Output is correct |
| 7 |
Correct |
202 ms |
16700 KB |
Output is correct |
| 8 |
Correct |
255 ms |
17016 KB |
Output is correct |
| 9 |
Correct |
339 ms |
17144 KB |
Output is correct |
| 10 |
Correct |
327 ms |
17252 KB |
Output is correct |
| 11 |
Correct |
311 ms |
17144 KB |
Output is correct |
| 12 |
Correct |
302 ms |
17144 KB |
Output is correct |
| 13 |
Correct |
311 ms |
17240 KB |
Output is correct |
| 14 |
Correct |
276 ms |
16888 KB |
Output is correct |
| 15 |
Correct |
281 ms |
16668 KB |
Output is correct |
| 16 |
Correct |
226 ms |
16632 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
176 ms |
15148 KB |
Output is correct |
| 2 |
Correct |
228 ms |
16788 KB |
Output is correct |
| 3 |
Correct |
217 ms |
16772 KB |
Output is correct |
| 4 |
Correct |
161 ms |
16760 KB |
Output is correct |
| 5 |
Correct |
349 ms |
17072 KB |
Output is correct |
| 6 |
Correct |
332 ms |
17352 KB |
Output is correct |
| 7 |
Correct |
305 ms |
17392 KB |
Output is correct |
| 8 |
Correct |
304 ms |
17380 KB |
Output is correct |
| 9 |
Correct |
271 ms |
17244 KB |
Output is correct |
| 10 |
Correct |
274 ms |
17140 KB |
Output is correct |
| 11 |
Correct |
301 ms |
17116 KB |
Output is correct |
| 12 |
Correct |
275 ms |
17272 KB |
Output is correct |
| 13 |
Correct |
290 ms |
17272 KB |
Output is correct |
| 14 |
Correct |
281 ms |
17272 KB |
Output is correct |
| 15 |
Correct |
312 ms |
17388 KB |
Output is correct |
| 16 |
Correct |
300 ms |
17364 KB |
Output is correct |
| 17 |
Correct |
285 ms |
17312 KB |
Output is correct |
| 18 |
Correct |
244 ms |
17176 KB |
Output is correct |
| 19 |
Correct |
275 ms |
17160 KB |
Output is correct |
| 20 |
Correct |
235 ms |
17112 KB |
Output is correct |
| 21 |
Correct |
178 ms |
16904 KB |
Output is correct |
| 22 |
Correct |
191 ms |
16872 KB |
Output is correct |
| 23 |
Correct |
200 ms |
16808 KB |
Output is correct |
