Submission #35816925

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

template<typename T>
vector<array<T, 2>> merge(vector<array<T, 2>> v) {
    if (v.empty())
        return {};

    sort(v.begin(), v.end());

    vector<array<T, 2>> tmp;

    tmp.push_back(v[0]);

    for (auto [l, r] : v) {
        auto &[l1, r1] = tmp.back();

        if (l <= r1) {
            r1 = max(r1, r);
        } else {
            tmp.push_back({l, r});
        }
    }

    return tmp;
};

template<typename T>
vector<array<T, 2>> filter(vector<array<T, 2>> v) {
    if (v.empty())
        return {};

    sort(v.begin(), v.end());

    vector<array<T, 2>> tmp;

    tmp.push_back(v[0]);

    for (auto [l, r] : v) {
        auto &[l1, r1] = tmp.back();

        if (r <= r1)
            continue;

        if (l == l1)
            tmp.pop_back();

        tmp.push_back({l, r});
    }

    return tmp;
};

template<typename T>
int getPos(const vector<array<T, 2>> &v, T x) {
    if (v.empty())
        return -1;

    auto p = lower_bound(v.begin(), v.end(), array<T, 2> {x + 1, numeric_limits<T>::min()});

    if (p == v.begin())
        return -1;

    p = prev(p);

    if ((*p)[1] < x)
        return -1;

    return p - v.begin();
};

int main() {
    cin.tie(NULL)->ios_base::sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 2>> elevators;
    vector<vector<array<int, 2>>> e(n + 1);

    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        e[a].push_back({b, c});
    }

    for (auto &v : e) {
        v = merge(v);
        elevators.insert(elevators.end(), v.begin(), v.end());
    }

    elevators = filter(elevators);
    m = elevators.size();

    int lg = log2(m) + 1;
    auto f = vector(lg, vector(m, 0));

    for (int i = 0, j = 0; i < m; ++i) {
        while (j + 1 < m && elevators[j + 1][0] <= elevators[i][1])
            ++j;

        f[0][i] = j;
    }

    for (int i = 1; i < lg; ++i) {
        for (int j = 0; j < m; ++j) {
            f[i][j] = f[i - 1][f[i - 1][j]];
        }
    }

    for (int i = 1; i <= q; ++i) {
        int a, b, x, y;
        cin >> a >> x >> b >> y;

        if (x > y) {
            swap(a, b);
            swap(x, y);
        }

        int ans = y - x;

        if (int p = getPos(e[a], x); p != -1) {
            x = e[a][p][1];
        }

        if (int p = getPos(e[b], y); p != -1) {
            y = e[b][p][0];
        }

        if (y <= x) {
            cout << ans + (a != b) << "\n";
            continue;
        }

        int p = getPos(elevators, x);

        if (p == -1) {
            cout << -1 << "\n";
            continue;
        }

        ++ans;
        x = elevators[p][1];

        if (x >= y) {
            cout << ans + 1 << "\n";
            continue;
        }

        for (int i = lg - 1; i >= 0; --i) {
            if (elevators[f[i][p]][1] < y) {
                p = f[i][p];
                ans += 1 << i;
            }
        }

        ++ans;
        p = f[0][p];
        x = elevators[p][1];

        if (x < y) {
            cout << -1 << "\n";
        } else {
            cout << ans + 1 << "\n";
        }
    }

    return 0;
}

Submission Info

Judge Result