Submission #265512

#	Time	Username	Problem	Language	Result	Execution time	Memory
265512		ainta	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	539 ms	18040 KiB

railway_trip

#include<cstdio>
#include<algorithm>
using namespace std;
int w[101000], n,K,Q, st[101000], Left[101000][19], Right[101000][19], INF = 1e9;
int Go(int b, int e){
    if(b==e)return 0;
    int l = b, r = b, s = 0;
    for(int i=17;i>=0;i--){
        int t1=min(Left[l][i],Left[r][i]);
        int t2=max(Right[l][i],Right[r][i]);
        if((b<e && t2<e) || (b>e && t1>e)){
            l=t1,r=t2;
            s+=(1<<i);
        }
    }
    int p1 = min(Left[l][0],Left[r][0]);
    int p2 = max(Right[l][0],Right[r][0]);
    if(p1==e||p2==e)return s+1;
    return INF;
}
int Calc(int b, int e){
    int tl = b, tr = b, s = 0, r1, r2;
    for(int i=17;i>=0;i--){
        int t1=min(Left[tl][i],Left[tr][i]);
        int t2=max(Right[tl][i],Right[tr][i]);
        if((b<e && t2<e) || (b>e && t1>e)){
            tl = t1, tr = t2;
            s+=(1<<i);
        }
    }
    r1 = min(Go(e,tl), Go(e,tr)) + s;
    int p1 = min(Left[tl][0],Left[tr][0]);
    int p2 = max(Right[tl][0],Right[tr][0]);
    r2 = min(Go(e,p1),Go(e,p2)) + s + 1;
    return min(r1,r2);
}
int main(){
    int i, j, top=0;
    scanf("%d%d%d",&n,&K,&Q);
    for(i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    w[0]=w[n+1]=1e9;
    for(i=0;i<=n;i++){
        while(top && w[st[top]]<w[i])top--;
        if(i)Left[i][0] = st[top];
        if(top && w[st[top]]==w[i])top--;
        st[++top]=i;
    }
    top=0;
    Right[n+1][0]=n+1;
    for(i=n+1;i>=0;i--){
        while(top && w[st[top]]<w[i])top--;
        if(i!=n+1)Right[i][0] = st[top];
        if(top && w[st[top]]==w[i])top--;
        st[++top]=i;
    }
    Left[1][0]=1,Right[n][0]=n;
    for(i=0;i<18;i++){
        for(j=1;j<=n;j++){
            Left[j][i+1]=min(Left[Left[j][i]][i], Left[Right[j][i]][i]);
            Right[j][i+1]=max(Right[Right[j][i]][i], Right[Left[j][i]][i]);
        }
    }
    while(Q--){
        int l, r;
        scanf("%d%d",&l,&r);
        int r1 = Calc(l,r);
        int r2 = Calc(r,l);
        printf("%d\n",min(r1,r2)-1);
    }
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |     scanf("%d%d%d",&n,&K,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%d",&w[i]);
      |         ~~~~~^~~~~~~~~~~~
railway_trip.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         scanf("%d%d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~

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