oj.uz

Submission #948604

# Submission time Handle Problem Language Result Execution time Memory
948604 2024-03-18T08:35:52 Z Hugo1729 Railway Trip (JOI17_railway_trip) C++11
100 / 100
 124 ms 16916 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=100000, MAXL=17;

int mleft[MAXN][MAXL], mright[MAXN][MAXL];

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n,k,q; cin >> n >> k >> q;
    vector<int> stations(n);
    for(int i=0;i<n;i++)cin >> stations[i];

    stack<pair<int,int>> monotonic1,monotonic2;

    for(int i=0;i<n;i++){
        while(monotonic1.size()>0&&monotonic1.top().first<stations[i]){
            monotonic1.pop();
        }
        if(monotonic1.empty()){
            mleft[i][0]=i;
        } else{
            mleft[i][0]=monotonic1.top().second;
        }
        monotonic1.push({stations[i],i});
    }

    for(int i=n-1;i>=0;i--){
        while(monotonic2.size()>0&&monotonic2.top().first<stations[i]){
            monotonic2.pop();
        }
        if(monotonic2.empty()){
            mright[i][0]=i;
        } else{
            mright[i][0]=monotonic2.top().second;
        }
        // cout << i << ' ' << mleft[i][0] << ' ' << mright[i][0] << '\n';
        monotonic2.push({stations[i],i});
    }

    for(int j=1;j<MAXL;j++){
        for(int i=0;i<n;i++){
            mleft[i][j]=min(mleft[mleft[i][j-1]][j-1],mleft[mright[i][j-1]][j-1]);
            mright[i][j]=max(mright[mright[i][j-1]][j-1],mright[mleft[i][j-1]][j-1]);
        }
    }

    while(q--){
        int a,b; cin >> a >> b;a--;b--;
        if(a>b)swap(a,b);

        int ans=0,l=a,r=a;

        for(int j=MAXL-1;j>=0;j--){
            int nl=min(mleft[l][j],mleft[r][j]),nr=max(mright[l][j],mright[r][j]);
            if(nr<b){
                l=nl;r=nr;
                ans+=(1<<j);
                // cout << "a " << j << ' ' << l << ' ' << r << '\n';
            }
        }

        a=r;
        l=b;
        r=b;

        for(int j=MAXL-1;j>=0;j--){
            int nl=min(mleft[l][j],mleft[r][j]),nr=max(mright[l][j],mright[r][j]);
            if(nl>a){
                l=nl;r=nr;
                ans+=(1<<j);
                // cout << "b " << j << ' ' << l << ' ' << r << '\n';
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2520 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 16 ms 14428 KB Output is correct
3 Correct 16 ms 14428 KB Output is correct
4 Correct 17 ms 14428 KB Output is correct
5 Correct 18 ms 14428 KB Output is correct
6 Correct 18 ms 14380 KB Output is correct
7 Correct 20 ms 14560 KB Output is correct
8 Correct 17 ms 15448 KB Output is correct
9 Correct 19 ms 14948 KB Output is correct
10 Correct 18 ms 14940 KB Output is correct
11 Correct 22 ms 14940 KB Output is correct
12 Correct 22 ms 14940 KB Output is correct
13 Correct 22 ms 14940 KB Output is correct
14 Correct 21 ms 15192 KB Output is correct
15 Correct 21 ms 14908 KB Output is correct
16 Correct 22 ms 14940 KB Output is correct
17 Correct 19 ms 14516 KB Output is correct
18 Correct 20 ms 14684 KB Output is correct
19 Correct 19 ms 14580 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 15952 KB Output is correct
2 Correct 102 ms 15956 KB Output is correct
3 Correct 67 ms 16148 KB Output is correct
4 Correct 66 ms 15956 KB Output is correct
5 Correct 67 ms 15956 KB Output is correct
6 Correct 70 ms 15952 KB Output is correct
7 Correct 68 ms 16100 KB Output is correct
8 Correct 75 ms 16724 KB Output is correct
9 Correct 124 ms 16916 KB Output is correct
10 Correct 97 ms 16724 KB Output is correct
11 Correct 121 ms 16884 KB Output is correct
12 Correct 92 ms 16748 KB Output is correct
13 Correct 93 ms 16724 KB Output is correct
14 Correct 93 ms 15980 KB Output is correct
15 Correct 72 ms 15956 KB Output is correct
16 Correct 63 ms 15700 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 16140 KB Output is correct
2 Correct 56 ms 15956 KB Output is correct
3 Correct 63 ms 16180 KB Output is correct
4 Correct 55 ms 16116 KB Output is correct
5 Correct 94 ms 16720 KB Output is correct
6 Correct 80 ms 16632 KB Output is correct
7 Correct 80 ms 16852 KB Output is correct
8 Correct 82 ms 16688 KB Output is correct
9 Correct 77 ms 16468 KB Output is correct
10 Correct 76 ms 16468 KB Output is correct
11 Correct 90 ms 16868 KB Output is correct
12 Correct 74 ms 16508 KB Output is correct
13 Correct 75 ms 16464 KB Output is correct
14 Correct 77 ms 16536 KB Output is correct
15 Correct 78 ms 16728 KB Output is correct
16 Correct 79 ms 16724 KB Output is correct
17 Correct 77 ms 16440 KB Output is correct
18 Correct 86 ms 16496 KB Output is correct
19 Correct 78 ms 16508 KB Output is correct
20 Correct 66 ms 16208 KB Output is correct
21 Correct 55 ms 15956 KB Output is correct
22 Correct 54 ms 15956 KB Output is correct
23 Correct 54 ms 16016 KB Output is correct