Submission #1194316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194316		LucaIlie	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	63 ms	28084 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct station {
    int nxt, best;
    bool operator<(const station &x) const {
        return best < x.best;
    }
};

struct train {
    int a, b;
    bool operator<(const train &x) const {
        if (b == x.b)
            return a < x.a;
        return b < x.b;
    }
};

const int MAX_N = 1e5;
const int MAX_LOG_N = 16;
const int MAX_M = 2e5;
train trains[MAX_M];
station maxReachGlobal[MAX_LOG_N + 1][MAX_N + 1];
int reachByOneTrain[MAX_N + 1];
int nextStationRight[MAX_LOG_N + 1][MAX_N + 1];
priority_queue<train> bestTrains;
vector<train> trainsByTime[MAX_N + 1];

station queryMax(int l, int r) {
    int p = log2(r - l + 1);
    return max(maxReachGlobal[p][l], maxReachGlobal[p][r - (1 << p) + 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, m;
    cin >> n >> k >> m;
    for (int i = 0; i < m; i++) {
        cin >> trains[i].a >> trains[i].b;
        trainsByTime[min(n, trains[i].a + k - 1)].push_back(trains[i]);
    }

    for (int i = n; i >= 1; i--) {
        maxReachGlobal[0][i] = {i, i};
        reachByOneTrain[i] = i;

        for (train t: trainsByTime[i])
            bestTrains.push(t);

        while (!bestTrains.empty() && bestTrains.top().a > i)
            bestTrains.pop();

        if (!bestTrains.empty()) {
            reachByOneTrain[i] = bestTrains.top().b;
            /* printf("one train %d %d\n", i, reachByOneTrain[i]); */
            maxReachGlobal[0][i] = queryMax(i, reachByOneTrain[i]);
        }

        nextStationRight[0][i] = maxReachGlobal[0][i].nxt;
        maxReachGlobal[0][i].nxt = i;
        for (int l = 1; (1 << l) <= n - i + 1; l++)
            maxReachGlobal[l][i] = max(maxReachGlobal[l - 1][i], maxReachGlobal[l - 1][i + (1 << (l - 1))]);

        /* printf("next %d %d\n", i, nextStationRight[0][i]); */
    }
    for (int l = 1; (1 << l) <= n; l++) {
        for (int i = 1; i <= n; i++)
            nextStationRight[l][i] = nextStationRight[l - 1][nextStationRight[l - 1][i]];
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        int ans = 0;
        for (int l = log2(n); l >= 0; l--) {
            if (reachByOneTrain[nextStationRight[l][a]] < b) {
                ans += (1 << l);
                a = nextStationRight[l][a];
            }
        }
        if (reachByOneTrain[nextStationRight[0][a]] < b)
            cout << "-1\n";
        else if (a >= b)
            cout << ans << "\n";
        else if (reachByOneTrain[a] >= b)
            cout << ans + 1 << "\n";
        else
            cout << ans + 2 << "\n";
    }

    return 0;
}

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