oj.uz

Submission #620482

# Submission time Handle Problem Language Result Execution time Memory
620482 2022-08-03T06:24:43 Z 이동현(#8521) Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 10572 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int NS = (int)1e5 + 4;

int n, k, q;
int a[NS];
vector<int> way[NS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k >> q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    vector<vector<int>> stk;
    for(int i = 1; i <= n; ++i){
        while((int)stk.size() && stk.back()[0] < a[i]){
            way[i].push_back(stk.back()[1]);

            stk.pop_back();
        }

        if((int)stk.size()){
            way[i].push_back(stk.back()[1]);

            if(stk.back()[0] == a[i]){
                stk.pop_back();
            }
        }

        stk.push_back({a[i], i});
    }

    stk.clear();
    for(int i = n; i >= 1; --i){
        while((int)stk.size() && stk.back()[0] < a[i]){
            way[i].push_back(stk.back()[1]);

            stk.pop_back();
        }

        if((int)stk.size()){
            way[i].push_back(stk.back()[1]);

            if(stk.back()[0] == a[i]){
                stk.pop_back();
            }
        }

        stk.push_back({a[i], i});
    }

    while(q--){
        int s, e; cin >> s >> e;

        vector<int> dist(n + 1);
        queue<int> que;

        dist[s] = 1;
        que.push(s);

        while(!que.empty()){
            int now = que.front();
            que.pop();

            for(auto&nxt:way[now]){
                if(dist[nxt]){
                    continue;
                }

                dist[nxt] = dist[now] + 1;
                que.push(nxt);
            }
        }

        cout << dist[e] - 2 << '\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 171 ms 9656 KB Output is correct
3 Correct 186 ms 9892 KB Output is correct
4 Correct 199 ms 10136 KB Output is correct
5 Correct 200 ms 10176 KB Output is correct
6 Correct 265 ms 10328 KB Output is correct
7 Correct 240 ms 10452 KB Output is correct
8 Correct 71 ms 7320 KB Output is correct
9 Correct 70 ms 9308 KB Output is correct
10 Correct 70 ms 8456 KB Output is correct
11 Correct 148 ms 9180 KB Output is correct
12 Correct 159 ms 9276 KB Output is correct
13 Correct 152 ms 9284 KB Output is correct
14 Correct 158 ms 9164 KB Output is correct
15 Correct 147 ms 9412 KB Output is correct
16 Correct 146 ms 9276 KB Output is correct
17 Correct 236 ms 10472 KB Output is correct
18 Correct 293 ms 10464 KB Output is correct
19 Correct 142 ms 10424 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 9764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 10572 KB Time limit exceeded
2 Halted 0 ms 0 KB -