oj.uz

Submission #265512

# Submission time Handle Problem Language Result Execution time Memory
265512 2020-08-14T23:07:39 Z ainta Railway Trip (JOI17_railway_trip) C++17
100 / 100
 539 ms 18040 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 256 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 57 ms 15744 KB Output is correct
3 Correct 51 ms 15872 KB Output is correct
4 Correct 51 ms 15864 KB Output is correct
5 Correct 48 ms 15872 KB Output is correct
6 Correct 48 ms 15992 KB Output is correct
7 Correct 51 ms 16248 KB Output is correct
8 Correct 49 ms 15744 KB Output is correct
9 Correct 49 ms 16256 KB Output is correct
10 Correct 50 ms 16128 KB Output is correct
11 Correct 58 ms 16256 KB Output is correct
12 Correct 61 ms 16248 KB Output is correct
13 Correct 64 ms 16228 KB Output is correct
14 Correct 59 ms 16256 KB Output is correct
15 Correct 59 ms 16256 KB Output is correct
16 Correct 60 ms 16248 KB Output is correct
17 Correct 48 ms 16128 KB Output is correct
18 Correct 48 ms 16248 KB Output is correct
19 Correct 49 ms 16248 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 17572 KB Output is correct
2 Correct 397 ms 17400 KB Output is correct
3 Correct 345 ms 17432 KB Output is correct
4 Correct 339 ms 17400 KB Output is correct
5 Correct 340 ms 17400 KB Output is correct
6 Correct 340 ms 17656 KB Output is correct
7 Correct 359 ms 17528 KB Output is correct
8 Correct 482 ms 17784 KB Output is correct
9 Correct 518 ms 17528 KB Output is correct
10 Correct 539 ms 17528 KB Output is correct
11 Correct 518 ms 17532 KB Output is correct
12 Correct 513 ms 17656 KB Output is correct
13 Correct 529 ms 17528 KB Output is correct
14 Correct 444 ms 17400 KB Output is correct
15 Correct 314 ms 17528 KB Output is correct
16 Correct 320 ms 17528 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 17656 KB Output is correct
2 Correct 230 ms 17656 KB Output is correct
3 Correct 240 ms 17528 KB Output is correct
4 Correct 236 ms 17536 KB Output is correct
5 Correct 515 ms 17624 KB Output is correct
6 Correct 322 ms 17916 KB Output is correct
7 Correct 310 ms 17912 KB Output is correct
8 Correct 343 ms 17912 KB Output is correct
9 Correct 310 ms 17912 KB Output is correct
10 Correct 309 ms 17912 KB Output is correct
11 Correct 309 ms 17788 KB Output is correct
12 Correct 315 ms 17912 KB Output is correct
13 Correct 314 ms 17916 KB Output is correct
14 Correct 307 ms 18040 KB Output is correct
15 Correct 314 ms 18040 KB Output is correct
16 Correct 313 ms 18028 KB Output is correct
17 Correct 313 ms 18032 KB Output is correct
18 Correct 327 ms 17852 KB Output is correct
19 Correct 326 ms 17912 KB Output is correct
20 Correct 308 ms 17784 KB Output is correct
21 Correct 227 ms 17656 KB Output is correct
22 Correct 228 ms 17656 KB Output is correct
23 Correct 257 ms 17528 KB Output is correct