线段树优化建图 + 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