T0459 走迷宫

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// 「下一个还没被回答的下标」的并查集：回答过的出口直接从链上摘掉
struct NextDSU {
    vector<int> p;
    explicit NextDSU(int n) : p(n + 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    void erase(int x) { p[x] = find(x + 1); }
};

struct State {
    ll x, y;
    int d;
};

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

    int n, m;
    ll sx, sy;
    cin >> n >> m >> sx >> sy;

    vector<pair<ll, ll>> obs(n);
    for (auto &o : obs) cin >> o.first >> o.second;
    vector<pair<ll, ll>> ex(m);
    for (auto &e : ex) cin >> e.first >> e.second;

    // 每一行的障碍 x（递增）、每一列的障碍 y（递增）
    map<ll, vector<ll>> rowObs, colObs;
    for (auto &o : obs) {
        rowObs[o.second].push_back(o.first);
        colObs[o.first].push_back(o.second);
    }
    for (auto &kv : rowObs) sort(kv.second.begin(), kv.second.end());
    for (auto &kv : colObs) sort(kv.second.begin(), kv.second.end());

    // 出口按 (y,x) 和 (x,y) 各排一份，分别用于横向和纵向的松弛
    vector<int> ordH(m), ordV(m);
    iota(ordH.begin(), ordH.end(), 0);
    iota(ordV.begin(), ordV.end(), 0);
    sort(ordH.begin(), ordH.end(), [&](int i, int j) {
        return ex[i].second != ex[j].second ? ex[i].second < ex[j].second : ex[i].first < ex[j].first;
    });
    sort(ordV.begin(), ordV.end(), [&](int i, int j) {
        return ex[i].first != ex[j].first ? ex[i].first < ex[j].first : ex[i].second < ex[j].second;
    });
    NextDSU dsuH(m), dsuV(m);
    vector<ll> answer(m, -1);
    // 出口正好就在起点：一步都不用走
    for (int i = 0; i < m; i++) {
        if (ex[i].first == sx && ex[i].second == sy) answer[i] = 0;
    }

    // 在 ordH 中找到第一个 (行, 列) >= (ry, rx) 的位置
    auto lowerH = [&](ll ry, ll rx) {
        int lo = 0, hi = m;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            ll my = ex[ordH[mid]].second, mx = ex[ordH[mid]].first;
            if (my < ry || (my == ry && mx < rx)) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    auto lowerV = [&](ll rx, ll ry) {
        int lo = 0, hi = m;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            ll mx = ex[ordV[mid]].first, my = ex[ordV[mid]].second;
            if (mx < rx || (mx == rx && my < ry)) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };

    // 把这一趟滑行经过的出口答案更新为 cost（BFS 保证第一次赋值就是最小值）
    auto relaxH = [&](ll ry, ll lo, ll hi, ll cost) {
        int i = dsuH.find(lowerH(ry, lo));
        while (i < m) {
            ll my = ex[ordH[i]].second, mx = ex[ordH[i]].first;
            if (my != ry || mx > hi) break;
            // BFS 保证第一次赋值就是最小步数；已答过的出口只从链上摘掉
            if (answer[ordH[i]] == -1) answer[ordH[i]] = cost;
            dsuH.erase(i);
            i = dsuH.find(i);
        }
    };
    auto relaxV = [&](ll rx, ll lo, ll hi, ll cost) {
        int i = dsuV.find(lowerV(rx, lo));
        while (i < m) {
            ll mx = ex[ordV[i]].first, my = ex[ordV[i]].second;
            if (mx != rx || my > hi) break;
            // BFS 保证第一次赋值就是最小步数；已答过的出口只从链上摘掉
            if (answer[ordV[i]] == -1) answer[ordV[i]] = cost;
            dsuV.erase(i);
            i = dsuV.find(i);
        }
    };

    auto keyOf = [](ll x, ll y, int d) -> unsigned long long {
        unsigned long long h = 1469598103934665603ULL;
        auto mix = [&](unsigned long long v) {
            h ^= v;
            h *= 1099511628211ULL;
        };
        mix((unsigned long long)x);
        mix((unsigned long long)y);
        mix((unsigned long long)d);
        return h;
    };

    const ll INF = (ll)4e18;
    unordered_map<unsigned long long, int> dist;
    queue<State> q;
    for (int d = 0; d < 4; d++) {
        dist[keyOf(sx, sy, d)] = 0;
        q.push({sx, sy, d});
    }

    while (!q.empty()) {
        State cur = q.front();
        q.pop();
        int steps = dist[keyOf(cur.x, cur.y, cur.d)];
        ll x = cur.x, y = cur.y;
        int d = cur.d;

        ll lx = x, ly = y;      // 落点
        ll lo = 0, hi = 0;      // 这一趟经过的区间（含出发点）
        bool blocked = false;   // 方向上有没有障碍

        if (d == 0 || d == 2) {
            // 横向滑行：找这一行里最近的障碍
            ll left = -INF, right = INF;
            auto it = rowObs.find(y);
            if (it != rowObs.end()) {
                const vector<ll> &v = it->second;
                // 第一个 >= x 的障碍：它在 x 的右边；它的前一个在 x 的左边
                auto p = lower_bound(v.begin(), v.end(), x);
                if (p != v.end()) right = *p;
                if (p != v.begin()) left = *(p - 1);
            }
            if (d == 0) {
                lo = x;
                hi = (right == INF) ? INF : right - 1;
                if (right != INF) {
                    blocked = true;
                    lx = right - 1;
                }
            } else {
                lo = (left == -INF) ? -INF : left + 1;
                hi = x;
                if (left != -INF) {
                    blocked = true;
                    lx = left + 1;
                }
            }
            relaxH(y, lo, hi, steps + 1);
        } else {
            // 纵向滑行：找这一列里最近的障碍
            ll down = -INF, up = INF;
            auto it = colObs.find(x);
            if (it != colObs.end()) {
                const vector<ll> &v = it->second;
                // 第一个 >= y 的障碍：它在 y 的上边；它的前一个在 y 的下边
                auto p = lower_bound(v.begin(), v.end(), y);
                if (p != v.end()) up = *p;
                if (p != v.begin()) down = *(p - 1);
            }
            if (d == 1) {
                lo = y;
                hi = (up == INF) ? INF : up - 1;
                if (up != INF) {
                    blocked = true;
                    ly = up - 1;
                }
            } else {
                lo = (down == -INF) ? -INF : down + 1;
                hi = y;
                if (down != -INF) {
                    blocked = true;
                    ly = down + 1;
                }
            }
            relaxV(x, lo, hi, steps + 1);
        }

        if (!blocked) continue;   // 这个方向没有障碍：滑向无穷远，不会再有下一站

        // 滑完之后只能左转或右转 90 度
        for (int nd : {(d + 1) % 4, (d + 3) % 4}) {
            unsigned long long key = keyOf(lx, ly, nd);
            if (dist.find(key) != dist.end()) continue;
            dist[key] = steps + 1;
            q.push({lx, ly, nd});
        }
    }

    for (ll v : answer) cout << v << "\n";
    return 0;
}