Submission #1092925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092925		Trisanu_Das	Railway Trip 2 (JOI22_ho_t4)	C++17	71 / 100	519 ms	70872 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct SegmentTree {
    int size;
    vector<pair<int, int>> seg;
    const pair<int, int> ID = {0, 0};

    pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
        if (a == ID) return b;
        if (b == ID) return a;
        int left = min(a.first, b.first);
        int right = max(a.second, b.second);
        return {left, right};
    }

    void init(int n, vector<pair<int, int>>& values) {
        size = 1;
        while (size < n) size <<= 1;
        seg.assign(2 * size + 2, ID);
        for (int i = 0; i < n; i++) seg[i + 1 + size] = values[i];
        for (int i = size - 1; i >= 1; i--) 
            seg[i] = combine(seg[i << 1], seg[(i << 1) + 1]);
    }

    pair<int, int> query(int a, int b, int x, int l, int r) {
        if (b < l || a > r) return ID;
        if (a <= l && b >= r) return seg[x];
        int mid = (l + r) >> 1;
        return combine(query(a, b, x << 1, l, mid), query(a, b, (x << 1) + 1, mid + 1, r));
    }

    pair<int, int> query(int a, int b) {
        return query(a, b, 1, 0, size - 1);
    }
};

const int MAX_N = 1e5 + 4;
const int MAX_M = 19;
pair<int, int> range[MAX_M][MAX_N];
vector<int> events[MAX_N];
SegmentTree segTree[MAX_M];

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

    int n, k;
    cin >> n >> k;

    int m;
    cin >> m;
    vector<pair<int, int>> lines(m);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        lines[i] = {a, b};

        if (a < b) {
            events[a].push_back(b);
            events[min(b + 1, a + k)].push_back(-b);
        } else {
            events[max(b, a - k + 1)].push_back(b);
            events[a + 1].push_back(-b);
        }
    }

    for (int i = 0; i <= n; i++) range[0][i] = {i, i};
    
    multiset<int> active_ranges;
    for (int i = 1; i <= n; i++) {
        for (auto event : events[i]) {
            if (event > 0) active_ranges.insert(event);
            else active_ranges.erase(active_ranges.find(-event));
        }

        if (!active_ranges.empty()) {
            auto it = active_ranges.end();
            --it;
            range[0][i] = {min(i, *active_ranges.begin()), max(i, *it)};
        }
    }

    {
        vector<pair<int, int>> values;
        for (int i = 1; i <= n; i++) values.push_back(range[0][i]);
        segTree[0].init(n, values);
    }

    for (int j = 1; j < MAX_M; j++) {
        vector<pair<int, int>> values;
        for (int i = 1; i <= n; i++) {
            int left = range[j - 1][i].first;
            int right = range[j - 1][i].second;
            range[j][i] = segTree[j - 1].query(left, right);
            values.push_back(range[j][i]);
        }
        segTree[j].init(n, values);
    }

    int q;
    cin >> q;

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

        if (t < range[MAX_M - 1][s].first || t > range[MAX_M - 1][s].second) {
            cout << "-1\n";
            continue;
        }

        int answer = 0;
        pair<int, int> current_range = {s, s};

        for (int j = MAX_M - 1; j >= 0; j--) {
            pair<int, int> new_range = segTree[j].query(current_range.first, current_range.second);
            if (t < new_range.first || t > new_range.second) {
                current_range = new_range;
                answer += (1 << j);
            }
        }

        cout << answer + 1 << "\n";
    }

    return 0;
}

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