oj.uz

Submission #1099006

# Submission time Handle Problem Language Result Execution time Memory
1099006 2024-10-10T12:07:50 Z thangdz2k7 Railway Trip (JOI17_railway_trip) C++17
100 / 100
 94 ms 18768 KB 
// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, k, q, a[N];
int l[N][LG], r[N][LG];

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

    l[1][0] = 1;
    for (int i = 2; i <= n; ++ i){
        l[i][0] = i - 1;
        while (a[i] > a[l[i][0]]) l[i][0] = l[l[i][0]][0];
    }
    r[n][0] = n;
    for (int i = n - 1; i >= 1; -- i){
        r[i][0] = i + 1;
        while (a[i] > a[r[i][0]]) r[i][0] = r[r[i][0]][0];
    }

    for (int lg = 1; lg < LG; ++ lg){
        for (int i = 1; i <= n; ++ i){
            int L = l[i][lg - 1], R = r[i][lg - 1];
            l[i][lg] = min(l[L][lg - 1], l[R][lg - 1]);
            r[i][lg] = max(r[L][lg - 1], r[R][lg - 1]);
        }
    }

    while (q --){
        int u, v; cin >> u >> v;
        if (u > v) swap(u, v); int ans = 0;
        int L = u, R = u;
        for (int lg = LG - 1; lg >= 0; -- lg){
            if (max(r[L][lg], r[R][lg]) < v){
                ans += (1 << lg);
                tie(L, R) = make_pair(min(l[L][lg], l[R][lg]), max(r[L][lg], r[R][lg]));
            }
        }

        u = R;
        L = v, R = v;
        for (int lg = LG - 1; lg >= 0; -- lg){
            if (min(l[L][lg], l[R][lg]) > u){
                ans += (1 << lg);
                tie(L, R) = make_pair(min(l[L][lg], l[R][lg]), max(r[L][lg], r[R][lg]));
            }
        }

        cout << ans << endl;
    }
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message

railway_trip.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
railway_trip.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
railway_trip.cpp:20:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
railway_trip.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 20 ms 16476 KB Output is correct
3 Correct 17 ms 16732 KB Output is correct
4 Correct 18 ms 16732 KB Output is correct
5 Correct 20 ms 16608 KB Output is correct
6 Correct 19 ms 16732 KB Output is correct
7 Correct 21 ms 17048 KB Output is correct
8 Correct 20 ms 16500 KB Output is correct
9 Correct 27 ms 16984 KB Output is correct
10 Correct 22 ms 16732 KB Output is correct
11 Correct 20 ms 16916 KB Output is correct
12 Correct 23 ms 16984 KB Output is correct
13 Correct 22 ms 16988 KB Output is correct
14 Correct 22 ms 16984 KB Output is correct
15 Correct 22 ms 16988 KB Output is correct
16 Correct 22 ms 16988 KB Output is correct
17 Correct 21 ms 17012 KB Output is correct
18 Correct 20 ms 16928 KB Output is correct
19 Correct 19 ms 16988 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 18128 KB Output is correct
2 Correct 67 ms 18256 KB Output is correct
3 Correct 67 ms 18144 KB Output is correct
4 Correct 64 ms 18260 KB Output is correct
5 Correct 68 ms 18260 KB Output is correct
6 Correct 64 ms 18252 KB Output is correct
7 Correct 67 ms 18260 KB Output is correct
8 Correct 73 ms 18260 KB Output is correct
9 Correct 90 ms 18256 KB Output is correct
10 Correct 84 ms 18260 KB Output is correct
11 Correct 94 ms 18260 KB Output is correct
12 Correct 80 ms 18260 KB Output is correct
13 Correct 86 ms 18296 KB Output is correct
14 Correct 76 ms 18256 KB Output is correct
15 Correct 76 ms 18260 KB Output is correct
16 Correct 59 ms 18004 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18384 KB Output is correct
2 Correct 49 ms 18272 KB Output is correct
3 Correct 53 ms 18256 KB Output is correct
4 Correct 55 ms 18256 KB Output is correct
5 Correct 94 ms 18256 KB Output is correct
6 Correct 80 ms 18652 KB Output is correct
7 Correct 76 ms 18768 KB Output is correct
8 Correct 77 ms 18516 KB Output is correct
9 Correct 86 ms 18512 KB Output is correct
10 Correct 72 ms 18516 KB Output is correct
11 Correct 76 ms 18512 KB Output is correct
12 Correct 73 ms 18516 KB Output is correct
13 Correct 80 ms 18544 KB Output is correct
14 Correct 78 ms 18512 KB Output is correct
15 Correct 80 ms 18744 KB Output is correct
16 Correct 82 ms 18516 KB Output is correct
17 Correct 82 ms 18676 KB Output is correct
18 Correct 79 ms 18640 KB Output is correct
19 Correct 79 ms 18528 KB Output is correct
20 Correct 84 ms 18512 KB Output is correct
21 Correct 52 ms 18256 KB Output is correct
22 Correct 52 ms 18256 KB Output is correct
23 Correct 51 ms 18476 KB Output is correct