Submission #363360

#	Time	Username	Problem	Language	Result	Execution time	Memory
363360		denkendoemeer	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	280 ms	18924 KiB

railway_trip

#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);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55