Submission #1675039

---

Source Code Expand

#include<bits/stdc++.h>
#define maxn 200100
#define inf 1000000007
using namespace std;
struct edge{
	int r,nxt;
}e[maxn*20];
typedef pair<int,int> par;
par A[2][maxn];
int rhead[maxn],low[maxn],n,L[maxn],val[maxn],R[maxn],tp,dfn[maxn];
int bel[maxn],insta[maxn],sta[maxn],tim,idL[maxn],idR[maxn],lc[maxn],rc[maxn],resz,head[maxn],esz,ptr,rt[2];
void addedge(int u,int v){
//	printf("[%d->%d]\n",u,v);
	e[++esz].r=v;e[esz].nxt=head[u];head[u]=esz;
}
void tarjan(int u){
	low[u]=dfn[u]=++tim,sta[++tp]=u,insta[u]=1;
	for(int t=head[u];t;t=e[t].nxt)
		if(!dfn[e[t].r])tarjan(e[t].r),low[u]=min(low[u],low[e[t].r]);
		else if(insta[e[t].r])low[u]=min(low[u],dfn[e[t].r]);
	if(low[u]==dfn[u]){
		int v;
		do{
			v=sta[tp--];
			insta[v]=0;
			bel[v]=u;
		}while(u!=v);
	}
}
int build(int d,int l,int r){
	if(l==r)return A[d][l].second;
	int mid=l+r>>1,rt=++ptr;
	lc[rt]=build(d,l,mid);
	rc[rt]=build(d,mid+1,r);
	addedge(rt,lc[rt]);
	addedge(rt,rc[rt]);
	return rt;
}
void qry(int o,int l,int r,int ql,int qr,int fr){
	if(ql>qr)return ;
	if(ql<=l&&r<=qr){
		addedge(fr,o);
		return ;
	}
	int mid=l+r>>1;
	if(ql<=mid)qry(lc[o],l,mid,ql,qr,fr);
	if(qr>mid)qry(rc[o],mid+1,r,ql,qr,fr);
}
bool chk(int d){
	for(int i=1;i<=ptr;++i)dfn[i]=low[i]=0,head[i]=rhead[i];
	esz=resz,tim=0;
	for(int i=1;i<=n;++i){
		int x=lower_bound(A[0]+1,A[0]+n+1,par(L[i]-d,-inf))-A[0];
		int y=upper_bound(A[0]+1,A[0]+n+1,par(L[i]+d,inf))-A[0]-1;
		if(idL[i]<x||y<idL[i])qry(rt[0],1,n,x,y,i<<1);
		else {	
			if(x<idL[i])qry(rt[0],1,n,x,idL[i]-1,i<<1);
			if(idL[i]<y)qry(rt[0],1,n,idL[i]+1,y,i<<1);
		}
		
		x=lower_bound(A[0]+1,A[0]+n+1,par(R[i]-d,-inf))-A[0];
		y=upper_bound(A[0]+1,A[0]+n+1,par(R[i]+d,inf))-A[0]-1;
		if(idL[i]<x||y<idL[i])qry(rt[0],1,n,x,y,i<<1|1);
		else {	
			if(x<idL[i])qry(rt[0],1,n,x,idL[i]-1,i<<1|1);
			if(idL[i]<y)qry(rt[0],1,n,idL[i]+1,y,i<<1|1);
		}
		
		x=lower_bound(A[1]+1,A[1]+n+1,par(R[i]-d,-inf))-A[1];
		y=upper_bound(A[1]+1,A[1]+n+1,par(R[i]+d,inf))-A[1]-1;
		if(idR[i]<x||y<idR[i])qry(rt[1],1,n,x,y,i<<1|1);
		else {	
			if(x<idR[i])qry(rt[1],1,n,x,idR[i]-1,i<<1|1);
			if(idR[i]<y)qry(rt[1],1,n,idR[i]+1,y,i<<1|1);
		}
		
		x=lower_bound(A[1]+1,A[1]+n+1,par(L[i]-d,-inf))-A[1];
		y=upper_bound(A[1]+1,A[1]+n+1,par(L[i]+d,inf))-A[1]-1;
		if(idR[i]<x||y<idR[i])qry(rt[1],1,n,x,y,i<<1);
		else {	
			if(x<idR[i])qry(rt[1],1,n,x,idR[i]-1,i<<1);
			if(idR[i]<y)qry(rt[1],1,n,idR[i]+1,y,i<<1);
		}
	}
	for(int i=1;i<=ptr;++i)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;++i)if(bel[i<<1]==bel[i<<1|1])return false;
	return true;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&L[i],&R[i]);
		if(L[i]>R[i])swap(L[i],R[i]);
		A[0][i]=par(L[i],i<<1|1);
		A[1][i]=par(R[i],i<<1);
		val[i<<1]=L[i],val[i<<1|1]=R[i];
	}
	ptr=2*n+1;
	sort(A[0]+1,A[0]+n+1);
	sort(A[1]+1,A[1]+n+1);
	for(int i=1;i<=n;++i)idL[A[0][i].second>>1]=i;
	for(int i=1;i<=n;++i)idR[A[1][i].second>>1]=i;
	rt[0]=build(0,1,n);
	rt[1]=build(1,1,n);
	for(int i=1;i<=ptr;++i)rhead[i]=head[i];
	resz=esz;
//	printf("[%d]",chk(3));
//	return 0;
	int l=1,r=1000000007,ans=0;
	while(l<=r){
		int mid=l+r>>1;
		if(chk(mid-1))ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d",ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:90:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:92:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&L[i],&R[i]);
                            ^

Judge Result