Submission #1800306

---

Source Code Expand

//二分答案+线段树优化建图+2_SAT
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200010
#define top 1000000000
using namespace std;

struct edge{int x, y, next;}a[10000010];
struct bb{int x, y;}b[N];
struct cc{int x, id;}c[N];
struct pos1{int l, r;}pos[N];
struct tt{int l, r;}t[N];
int n, L, R, mid, l, p[N], root[2], flag[N], dfn[N], low[N], ss, cl, d[N], l1, P[N], sum;

inline bool cmp(cc a, cc b){return a.x<b.x;}

inline void add(int x, int y){a[++l1].x=x; a[l1].y=y; a[l1].next=p[x]; p[x]=l1;}

inline void maketree(int L, int R, int temp){
	t[l].l=t[l].r=0;
	if(L<R){
		int mid=(L+R)>>1, l1=l;
		l++; t[l1].l=l; if(!temp)add(l1, l); else add(l, l1);
		maketree(L, mid, temp);
		l++; t[l1].r=l; if(!temp)add(l1, l); else add(l, l1);
		maketree(mid+1, R, temp);
	}else{
		if(!temp){
			int x=c[L].id&1?pos[(c[L].id+1)/2].r:pos[c[L].id/2].l;
			add(l, x);
		}else add(L, l);
	}
}

inline void ins(int i, int a, int b, int x, int temp, int L, int R){
	if(a<=L&&R<=b){if(!temp)add(x, i); else add(i, x); return;}
	int mid=(L+R)>>1;
	if(a<=mid)ins(t[i].l, a, b, x, temp, L, mid);
	if(mid<b)ins(t[i].r, a, b, x, temp, mid+1, R);
}

inline void tarjan(int x){
	dfn[x]=low[x]=++ss;
	flag[x]=1; d[++cl]=x;
	for(int i=p[x]; i; i=a[i].next){
		if(!flag[a[i].y])tarjan(a[i].y);
		if(flag[a[i].y]==1)low[x]=min(low[x], low[a[i].y]);
	}
	if(dfn[x]==low[x]){
		sum++;
		while(d[cl]!=x){flag[d[cl]]=2; P[d[cl]]=sum; cl--;}
		flag[x]=2; P[x]=sum; cl--;
	}
}

inline int check(int mid){
	l1=0; memset(p, 0, sizeof(p)); l=n*2;
	l++; root[0]=l; maketree(1, n*2, 0);
	l++; root[1]=l; maketree(1, n*2, 1);
	int L=1, R=1, x;
	for(int i=1; i<=n*2; i++){
		while(L<i&&c[i].x-c[L].x>=mid)L++;
		while(R<n*2&&c[R+1].x-c[i].x<mid)R++;
		x=c[i].id&1?pos[(c[i].id+1)/2].r:pos[c[i].id/2].l;
		if(L<i){
			ins(root[0], L, i-1, i, 0, 1, n*2);
			ins(root[1], L, i-1, x, 1, 1, n*2);
		}
		if(i<R){
			ins(root[0], i+1, R, i, 0, 1, n*2);
			ins(root[1], i+1, R, x, 1, 1, n*2);
		}
	}
	cl=ss=sum=0; memset(flag, 0, sizeof(flag));
	for(int i=1; i<=l; i++)if(!flag[i])tarjan(i);
	for(int i=1; i<=n; i++)if(P[pos[i].l]==P[pos[i].r])return 0;
	return 1;
}

int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; i++)scanf("%d%d", &b[i].x, &b[i].y);
	for(int i=1; i<=n; i++){
		c[i*2-1].x=b[i].x; c[i*2-1].id=i*2-1;
		c[i*2].x=b[i].y; c[i*2].id=i*2;
	}
	sort(c+1, c+1+n*2, cmp);
	for(int i=1; i<=n*2; i++)
		if(c[i].id&1)pos[(c[i].id+1)/2].l=i; else pos[c[i].id/2].r=i;
	L=0; R=top/(n-1);
	while(L<R){
		mid=(L+R)>>1; if(L==R-1)mid++;
		if(check(mid))L=mid; else R=mid-1;
	}
	printf("%d", L);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:82:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:83:56: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++)scanf("%d%d", &b[i].x, &b[i].y);
                                                        ^

Judge Result