Submission #363360

#TimeUsernameProblemLanguageResultExecution timeMemory
363360denkendoemeerRailway Trip (JOI17_railway_trip)C++14
100 / 100
280 ms18924 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...