제출 #1326892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326892		defactopdiddy	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	309 ms	31220 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int D = 18;

// Overlapping Iterative Segment Trees tracking bounds.
// st_L[d][x] stores the minimum station reachable from x in 2^d steps.
// st_R[d][x] stores the maximum station reachable from x in 2^d steps.
int st_L[D][MAXN * 2];
int st_R[D][MAXN * 2];
int N, K, M, Q;

int query_L(int d, int l, int r) {
    int res = 1e9;
    for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = min(res, st_L[d][l++]);
        if (r & 1) res = min(res, st_L[d][--r]);
    }
    return res;
}

int query_R(int d, int l, int r) {
    int res = -1e9;
    for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = max(res, st_R[d][l++]);
        if (r & 1) res = max(res, st_R[d][--r]);
    }
    return res;
}

int main() {
    // Fast I/O Operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> K >> M)) return 0;

    vector<int> MaxB(N, -1), MinB(N, 1e9);

    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;  // Mapping values to strictly 0-indexed values
        if (a < b) {
            MaxB[a] = max(MaxB[a], b);     // Capture largest spans optimally
        } else {
            MinB[a] = min(MinB[a], b);
        }
    }

    // Base segment trees resolving the very best 1-step train boarding ranges
    vector<int> st_maxB(2 * N, -1);
    vector<int> st_minB(2 * N, 1e9);

    for (int i = 0; i < N; ++i) {
        st_maxB[N + i] = MaxB[i];
        st_minB[N + i] = MinB[i];
    }
    for (int i = N - 1; i > 0; --i) {
        st_maxB[i] = max(st_maxB[i << 1], st_maxB[i << 1 | 1]);
        st_minB[i] = min(st_minB[i << 1], st_minB[i << 1 | 1]);
    }

    // Layer-0: Base cases for reaching exactly 1-step away mapping bounds
    for (int i = 0; i < N; ++i) {
        int r0 = i;
        int l_q = max(0, i - K + 1) + N;
        int r_q = i + N + 1;  // Right query boundaries: [max(0, i - K + 1), i]
        while (l_q < r_q) {
            if (l_q & 1) r0 = max(r0, st_maxB[l_q++]);
            if (r_q & 1) r0 = max(r0, st_maxB[--r_q]);
            l_q >>= 1; r_q >>= 1;
        }
        st_R[0][N + i] = r0;

        int l0 = i;
        l_q = i + N;
        r_q = min(N - 1, i + K - 1) + N + 1;  // Left query boundaries: [i, min(N - 1, i + K - 1)]
        while (l_q < r_q) {
            if (l_q & 1) l0 = min(l0, st_minB[l_q++]);
            if (r_q & 1) l0 = min(l0, st_minB[--r_q]);
            l_q >>= 1; r_q >>= 1;
        }
        st_L[0][N + i] = l0;
    }

    // Build upper properties of Layer-0 segment tree
    for (int i = N - 1; i > 0; --i) {
        st_L[0][i] = min(st_L[0][i << 1], st_L[0][i << 1 | 1]);
        st_R[0][i] = max(st_R[0][i << 1], st_R[0][i << 1 | 1]);
    }

    // Dynamic Programming expanding jump distances building Segment trees overlapping to D
    for (int d = 1; d < D; ++d) {
        for (int i = 0; i < N; ++i) {
            int l = st_L[d - 1][N + i];
            int r = st_R[d - 1][N + i];
            st_L[d][N + i] = query_L(d - 1, l, r);
            st_R[d][N + i] = query_R(d - 1, l, r);
        }
        for (int i = N - 1; i > 0; --i) {
            st_L[d][i] = min(st_L[d][i << 1], st_L[d][i << 1 | 1]);
            st_R[d][i] = max(st_R[d][i << 1], st_R[d][i << 1 | 1]);
        }
    }

    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int s, t;
        cin >> s >> t;
        --s; --t;

        if (s == t) {
            cout << 0 << "\n";
            continue;
        }

        // Checks if destination is wholly unreachable after maximum theoretical depths
        if (t < st_L[D - 1][N + s] || t > st_R[D - 1][N + s]) {
            cout << -1 << "\n";
            continue;
        }

        int ans = 0;
        int l = s, r = s;
        
        // Logarithmically evaluate step counts safely converging exact bounds
        for (int d = D - 1; d >= 0; --d) {
            int nl = query_L(d, l, r);
            int nr = query_R(d, l, r);
            // If the jump structurally doesn't cover T, firmly commit to taking it
            if (t < nl || t > nr) {
                ans += (1 << d);
                l = nl;
                r = nr;
            }
        }
        // Applying accumulated absolute skips prior to arrival offsets the final threshold jump
        cout << ans + 1 << "\n";
    }

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13