Submission #1676032

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls(x) ((x)<<1)
#define rs(x) (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
namespace SAT{
	const int maxn=200005,maxm=1e6;
	int tot,head[maxn],t[maxm],ne[maxm],num,n,dfn[maxn],low[maxn],S[maxn],top,clk,bl[maxn];
	bool vis[maxn],ins[maxn];
	inline void addedge(int x,int y){
		ne[++num]=head[x];head[x]=num;t[num]=y;
		// printf("%d %d\n",x,y);
	}
	inline void init(int _n){
		rep(i,2,2*_n+1)head[i]=-1;clk=0;tot=0;top=0;
		memset(vis,0,sizeof(vis));memset(ins,0,sizeof(ins));
		num=0;n=_n;
	}
	inline void tarjan(int x){
		low[x]=dfn[x]=++clk;vis[x]=1;S[++top]=x;ins[x]=1;
		forE(i,x)if(!vis[t[i]]){
			tarjan(t[i]);low[x]=min(low[x],low[t[i]]);
		}else if(ins[t[i]])
			low[x]=min(low[x],dfn[t[i]]);
		if(low[x]==dfn[x]){
			tot++;
			while(S[top]!=x){
				bl[S[top]]=tot;
				ins[S[top]]=0;
				top--;
			}
			bl[x]=tot;ins[x]=0;top--;
		}
	}
	inline bool check(){
		rep(i,2,2*n+1)if(!vis[i])tarjan(i);
		rep(i,1,n)if(bl[2*i]==bl[2*i+1])return 0;
		return 1;
	}
}
inline void addedge(int x,int y,int vx,int vy){
//	printf("%d %d %d %d\n",x,y,vx,vy);
	SAT::addedge(2*x+vx,2*y+vy);
	SAT::addedge(2*y+((vy)^1),2*x+(vx^1));
}
namespace seg{
	const int maxn=4e4;
	int id[maxn],tot,l[maxn],r[maxn];
	inline void build(int x,int lq,int rq){
		l[x]=lq;r[x]=rq;
		if(lq==rq){
			id[x]=lq;
			return;
		}id[x]=++tot;int md=(lq+rq)>>1;
		build(ls(x),lq,md);build(rs(x),md+1,rq);
	}
	inline void add(int x){
		if(l[x]==r[x])return;
		add(ls(x));add(rs(x));
		addedge(id[x],id[ls(x)],0,0);
		addedge(id[x],id[rs(x)],0,0);
	}
	inline void add(int x,int lq,int rq,int nd){
		if(lq>rq)return;
		if(lq<=l[x]&&r[x]<=rq){
			addedge(nd,id[x],1,0);
			return;
		}int md=(l[x]+r[x])>>1;
		if(lq<=md)add(ls(x),lq,rq,nd);
		if(rq> md)add(rs(x),lq,rq,nd);
	}
}
const int maxn=2e4;
int x[maxn],y[maxn];
int rkx[maxn],rky[maxn];
map<int,int> zb;
pin h[maxn<<1];
int n,tot,tr[maxn];
inline bool check(int v){
	// puts("===============================");
	// printf("!%d\n",v);
	SAT::init(seg::tot);
	// SAT::init(2*n);
	seg::add(1);
	rep(i,1,n)
		addedge(rkx[i],rky[i],1,0),addedge(rkx[i],rky[i],0,1);
	int j=1;
	rep(i,1,2*n){
		while(j<2*n&&tr[i]-tr[j]>=v)j++;
		// if(v==3)fprintf(stderr, "%d %d\n", i,j);
		seg::add(1,j,i-1,i);
		// rep(k,j,i-1)addedge(i,k,1,0);
	} j=2*n;
	per(i,2*n,1){
		while(j>1&&tr[j]-tr[i]>=v)j--;
		seg::add(1,i+1,j,i);
		// rep(k,i+1,j)addedge(i,k,1,0);
	}
	return SAT::check();
}
int main(){
	read(n);
	rep(i,1,n)read(x[i]),read(y[i]);
	rep(i,1,n)h[++tot]=mk(x[i],2*i),h[++tot]=mk(y[i],2*i+1);
	sort(h+1,h+1+tot);int now=0;
	rep(i,1,tot){
		if(h[i].w2&1)
			rky[h[i].w2/2]=i;
		else
			rkx[h[i].w2/2]=i;
	}
	rep(i,1,tot){
		tr[i]=h[i].w1;
	}
	seg::tot=2*n;seg::build(1,1,2*n);
	int l=0,r=1e9,ans=0;
	while(l<=r){
		int md=(l+r)>>1;
		if(check(md)){
			ans=md;
			l=md+1;
		}else{
			r=md-1;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result