Submission #1676848

---

Source Code Expand

#include<bits/stdc++.h>
#define N 300005
#define M 2000005
#define L(__) (__ << 1)
#define R(__) (L(__)|1)
using namespace std;
int n,m,x[N],wx[N],wy[N],head[N],nxt[M],num[M],a[N],ax[N],ay[N],nx[N],ny[N],dfn[N],low[N],dfs_clock,scc_cnt,scc[N],st[N],top;
void link(int x,int y){ num[++m]=y,nxt[m]=head[x],head[x]=m;}
bool cmp(int p,int q){ return x[p]<x[q];}
int Z(int x){ return x>n ? x-n : x+n;}
void B(int t,int l,int r)
{
	int mid=(l+r)>>1;
	if(l==r){
		link(t+2*n,Z(a[l]));
		link(a[l],t+10*n);
		return ;
	  }
	B(L(t),l,mid);
	B(R(t),mid+1,r);
	link(t+2*n,L(t)+2*n);
	link(t+2*n,R(t)+2*n);
	link(L(t)+10*n,t+10*n);
	link(R(t)+10*n,t+10*n);
}
void C(int t,int l,int r,int l1,int r1,int x)
{
	int mid=(l+r)>>1;
	if(l>r1 || r<l1) return ;
	if(l>=l1&&r<=r1){
		link(x,t+2*n);
		link(t+10*n,Z(x));
		return ;
	  }
	C(L(t),l,mid,l1,r1,x);
	C(R(t),mid+1,r,l1,r1,x);
}
void Tarjan(int t)
{
	int i; st[++top]=t;
	dfn[t]=low[t]=++dfs_clock;
	for(i=head[t];i;i=nxt[i])
		if(!dfn[num[i]]) Tarjan(num[i]),low[t]=min(low[t],low[num[i]]);
		else if(!scc[num[i]]) low[t]=min(low[t],dfn[num[i]]);
	if(dfn[t]==low[t]){
		++scc_cnt;
		while(1){
			scc[st[top]]=scc_cnt;
			if(st[top--]==t) break;
		  }
	  }
}
bool chk(int d)
{
	int i,l,r,p; m=0;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(scc,0,sizeof(scc));
	memset(head,0,sizeof(head));
	B(1,1,2*n);
	for(i=1;i<=2*n;i++){
		l=lower_bound(wx+1,wx+n+1,x[i]-d+1)-wx;
		r=upper_bound(wx+1,wx+n+1,x[i]+d-1)-wx-1;
		p=nx[i>n ? i-n : i];
		if(p>=l&&p<=r){
			if(l<p) C(1,1,2*n,l,p-1,i);
			if(p<r) C(1,1,2*n,p+1,r,i);
		  }
		else C(1,1,2*n,l,r,i);
		l=lower_bound(wy+1,wy+n+1,x[i]-d+1)-wy+n;
		r=upper_bound(wy+1,wy+n+1,x[i]+d-1)-wy-1+n;
		p=ny[i<=n ? i+n : i]+n;
		if(p>=l&&p<=r){
			if(l<p) C(1,1,2*n,l,p-1,i);
			if(p<r) C(1,1,2*n,p+1,r,i);
		  }
		else C(1,1,2*n,l,r,i);
	  }
	dfs_clock=top=scc_cnt=0;
	for(i=1;i<=18*n;i++)
		if(!dfn[i]) Tarjan(i);
	for(i=1;i<=n;i++)
		if(scc[i]==scc[i+n]) return 0;
	return 1;
}
int main()
{
	int i,l,r,mid;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d %d",&x[i],&x[i+n]),wx[i]=x[i],wy[i]=x[i+n],ax[i]=i,ay[i]=i+n;
	sort(ax+1,ax+n+1,cmp);
	sort(ay+1,ay+n+1,cmp);
	sort(wx+1,wx+n+1);
	sort(wy+1,wy+n+1);
	for(i=1;i<=n;i++) a[i]=ax[i],a[i+n]=ay[i];
	for(i=1;i<=n;i++) nx[ax[i]]=i,ny[ay[i]]=i;
	r=(int)(1e9),l=0;
	while(r-l>1){
		mid=(l+r)>>1;
		if(chk(mid)) l=mid;
		else r=mid;
	  }
	cout<<l;
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:89:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:91:73: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x[i],&x[i+n]),wx[i]=x[i],wy[i]=x[i+n],ax[i]=i,ay[i]=i+n;
                                                                         ^

Judge Result