评测记录

输出里有一个数是18，答案是19.

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
template<typename T>
void read(T& x){
	char c=getchar();bool a=0;x=0;
	while(!isdigit(c)){
		if(c=='-') a^=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	if(a) x*=-1;
	return;
}
template<typename T>
void read(T* x,T* y){
	while(x<y){
		read(*x);
		x++;
	}
	return;
}
template<typename T,typename ...Args>
void read(T& x,Args&... args){
	read(x),read(args...);
	return;
}
const int N=2e5+10;
int n,m,d;
int fa[N],dis[N],ans[N];
struct Pie{
	int s[2],id;
}p[N];
queue<int>q;
bool cmp1(Pie x,Pie y){
	if(x.s[0]<y.s[0]) return true;
	return false;
}
bool cmp2(Pie x,Pie y){
	if(x.s[1]<y.s[1]) return true;
	return false;
}
int find(int i){
	if(fa[i]==i) return i;
	return fa[i]=find(fa[i]);
}
void bfs(){
	sort(p+1,p+n+1,cmp2),sort(p+n+1,p+m+1,cmp1);
	for(int i=1;i<=m;i++){
		if(!p[i].s[i<=n]){
			q.push(i),dis[i]=1;
			//printf("push(%d)\n",i);
		}
	}
	while(!q.empty()){
		int i=q.front();q.pop();
		//printf("i=%d{%d,%d,%d}\n",i,p[i].s[0],p[i].s[1],p[i].id);
		int tmp=(i<=n?n:0),l=1+tmp,r=n+tmp,mid,L,R;
		while(l<r){
			mid=(l+r)>>1;
			if(p[mid].s[i>n]<p[i].s[i>n]-d) l=mid+1;
			else r=mid;
		}
		if(l==r) L=l;
		l=1+tmp,r=n+tmp;
		while(l<r){
			mid=(l+r+1)>>1;
			if(p[mid].s[i>n]>p[i].s[i>n]) r=mid-1;
			else l=mid;
		}
		if(l==r) R=l;
		//printf("[%d, %d]\n",L,R);
		if(!L||!R) continue;
		for(int j=L,tmp;j<=R;j=tmp+1){
			fa[tmp=find(j)]=find(R);
			if(!dis[j]){
				dis[j]=dis[i]+1;
				q.push(j);
			}
		}
	}
	return;
}
int main(){
	read(n,d),m=n<<1;
	for(int i=1,a,b;i<=m;i++){
		read(a,b),p[i]={a,b,i},fa[i]=i;
	}
	bfs();
	for(int i=1;i<=m;i++){
		ans[p[i].id]=dis[i];
	}
	for(int i=1;i<=n;i++){
		if(!ans[i]) printf("-1\n");
		else printf("%d\n",ans[i]);
	}
	return 0;
}