Submission #1194399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194399		LucaIlie	Railway Trip 2 (JOI22_ho_t4)	C++20	16 / 100	2095 ms	12340 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;
};

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

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

const int MAX_N = 1e5;
const int MAX_LOG_N = 16;
const int MAX_M = 2e5;
train trains[MAX_M];
priority_queue<leftTrain> bestLeftTrains;
priority_queue<rightTrain> bestRightTrains;
vector<train> leftTrainsByTime[MAX_N + 1], rightTrainsByTime[MAX_N + 1];
int minLeft[MAX_LOG_N + 1][MAX_N + 1], maxRight[MAX_LOG_N + 1][MAX_N + 1];

int queryMin(int p, int l, int r) {
    int minn = MAX_N;
    for (int i = l; i <= r; i++)
        minn = min(minn, minLeft[p][i]);
    return minn;
}

int queryMax(int p, int l, int r) {
    int maxx = 0;
    for (int i = l; i <= r; i++)
        maxx = max(maxx, maxRight[p][i]);
    return maxx;
}

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;
        if (trains[i].a < trains[i].b)
            rightTrainsByTime[min(n, trains[i].a + k - 1)].push_back(trains[i]);
        else
            leftTrainsByTime[max(1, trains[i].a - k + 1)].push_back(trains[i]);
    }

    for (int i = 1; i <= n; i++) {
        for (leftTrain t: leftTrainsByTime[i])
            bestLeftTrains.push(t);

        while (!bestLeftTrains.empty() && bestLeftTrains.top().a < i)
            bestLeftTrains.pop();

        minLeft[0][i] = i;
        if (!bestLeftTrains.empty())
            minLeft[0][i] = min(i, bestLeftTrains.top().b);
    }

    for (int i = n; i >= 1; i--) {
        for (rightTrain t: rightTrainsByTime[i])
            bestRightTrains.push(t);

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

        maxRight[0][i] = i;
        if (!bestRightTrains.empty())
            maxRight[0][i] = max(i, bestRightTrains.top().b);
    }

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

    for (int p = 1; p <= MAX_LOG_N; p++) {
        for (int i = 1; i <= n; i++) {
            int l = minLeft[p - 1][i], r = maxRight[p - 1][i];
            minLeft[p][i] = queryMin(p - 1, l, r);
            maxRight[p][i] = queryMax(p - 1, l, r);
        }
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        int l = a, r = a;
        int ans = 0;
        for (int p = MAX_LOG_N; p >= 0; p--) {
            int newL = queryMin(p, l, r);
            int newR = queryMax(p, l, r);
            if (newL <= b && b <= newR)
                continue;
            l = newL;
            r = newR;
            ans += (1 << p);
        }
        int newL = queryMin(0, l, r);
        int newR = queryMax(0, l, r);
        l = newL, r = newR;
        ans++;

        if (newL <= b && b <= newR)
            cout << ans << "\n";
        else
            cout << "-1\n";
    }

    return 0;
}

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