线段树优化建图 + dijkstra

#include<bits/stdc++.h>
#define N 610000
using namespace std;
int n, m, tot, ag[N], bg[N], ans[N];
int edge_id, head[N];
int ach[N][2], abh[N];
int bch[N][2], bbh[N];
struct node {
    int to, next, val;
} e[N];
void add_edge(int u, int v, int val) {
    // cout << "get : " << u << " " << v << endl;
    ++edge_id;
    e[edge_id].to = v;
    e[edge_id].next = head[u];
    e[edge_id].val = val;
    head[u] = edge_id;
}
struct SA {
    int a, b, id;
} A[N];
bool cmpa(SA aa, SA bb) {
    return aa.a < bb.a;
}
struct SB {
    int a, b;
} B[N];
bool cmpb(SB aa, SB bb) {
    return aa.a < bb.a;
}
void abuild(int L, int R, int id) {
    abh[id] = ++tot;
    int mid = (L + R) / 2;
    if(L == R) ag[L] = tot;
    else abuild(L, mid, id << 1), abuild(mid + 1, R, id << 1 | 1), 
        add_edge(abh[id << 1], abh[id], 0), add_edge(abh[id << 1 | 1], abh[id], 0);
}
void bbuild(int L, int R, int id) {
    bbh[id] = ++tot;
    int mid = (L + R) / 2;
    if(L == R) bg[L] = tot;
    else bbuild(L, mid, id << 1), bbuild(mid + 1, R, id << 1 | 1), 
        add_edge(bbh[id << 1], bbh[id], 0), add_edge(bbh[id << 1 | 1], bbh[id], 0);
}
int afindl(int x) {
    int L = 1, R = n, ans = -1;
    while(L <= R) {
        int mid = (L + R) / 2;
        if(x <= A[mid].a) R = mid - 1, ans = mid;
        else L = mid + 1;
    }
    return ans;
}
int afindr(int x) {
    int L = 1, R = n, ans = -1;
    while(L <= R) {
        int mid = (L + R) / 2;
        if(x >= A[mid].a) L = mid + 1, ans = mid;
        else R = mid - 1;
    }
    return ans;
}
int bfindl(int x) {
    int L = 1, R = n, ans = -1;
    while(L <= R) {
        int mid = (L + R) / 2;
        if(x <= B[mid].a) R = mid - 1, ans = mid;
        else L = mid + 1;
    }
    return ans;
}
int bfindr(int x) {
    int L = 1, R = n, ans = -1;
    while(L <= R) {
        int mid = (L + R) / 2;
        if(x >= B[mid].a) L = mid + 1, ans = mid;
        else R = mid - 1;
    }
    return ans;
}
void alb(int id, int L, int R, int l, int r, int bh) {
    if(l <= L && R <= r) {
        add_edge(abh[id], bh, 1);
        return;
    }
    int mid = (L + R) / 2;
    if(l <= mid) alb(id << 1, L, mid, l, r, bh);
    if(r > mid) alb(id << 1 | 1, mid + 1, R, l, r, bh);
}
void blb(int id, int L, int R, int l, int r, int bh) {
    if(l <= L && R <= r) {
        add_edge(bbh[id], bh, 1);
        return;
    }
    int mid = (L + R) / 2;
    if(l <= mid) blb(id << 1, L, mid, l, r, bh);
    if(r > mid) blb(id << 1 | 1, mid + 1, R, l, r, bh);
}
priority_queue< pair<int, int> > q;
int flag[N], tans[N];
void dij() {
    for(int i = 1; i <= tot; i++) ans[i] = 1e9;
    for(int i = 1; i <= n; i++) if(!A[i].b) ans[ag[i]] = 1, q.push(make_pair(-1, ag[i]));
    for(int i = 1; i <= n; i++) if(!B[i].b) ans[bg[i]] = 1, q.push(make_pair(-1, bg[i]));
    while(!q.empty()) {
        int u = q.top().second;
        q.pop();
        if(flag[u]) continue;
        else flag[u] = 1;
        for(int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if(ans[v] > ans[u] + e[i].val) ans[v] = ans[u] + e[i].val, q.push(make_pair(-ans[v], v));
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d%d", &A[i].a, &A[i].b), A[i].id = i;
    sort(A + 1, A + n + 1, cmpa);
    for(int i = 1; i <= n; i++) scanf("%d%d", &B[i].a, &B[i].b);
    sort(B + 1, B + n + 1, cmpb);
    abuild(1, n, 1), bbuild(1, n, 1);
    // cout << "-------------" << endl;
    for(int i = 1; i <= n; i++) {
        // if(A[i].b > B[n].a) continue;
        int L = bfindl(A[i].b), R = bfindr(A[i].b + m);
        if(L == -1 || R == -1) continue;
        // if(L > R) continue;
        // cout << A[i].b << " " << A[i].b + m << " is " << L << " " << R << endl;
        blb(1, 1, n, L, R, ag[i]);
    }
    // cout << "-------------" << endl;
    for(int i = 1; i <= n; i++) {
        // if(B[i].b > A[n].a) continue;
        int L = afindl(B[i].b), R = afindr(B[i].b + m);
        if(L == -1 || R == -1) continue;
        // if(L > R) continue;
        // cout << B[i].b << " " << B[i].b + m << " is " << L << " " << R << endl;
        alb(1, 1, n, L, R, bg[i]);
    }
    dij();
    for(int i = 1; i <= n; i++) tans[A[i].id] = ans[ag[i]];
    for(int i = 1; i <= n; i++) printf("%d\n", tans[i] == 1e9 ? -1 : tans[i]);
    return 0;
}

// 3 1
// 13 0
// 5 3
// 8 1
// 1 4
// 4 14
// 100 100