Submission #1118967

---

Source Code Expand

//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back 
#define MP make_pair
typedef long long ll;
const ll INF=1<<28;
const ll LINF=1ll<<61;
//My own input/output stream
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putsp()
#define putii(x,y) puti(x),putnum(y),putsp()
#define putiii(x,y,z) putii(x,y),putnum(z),putsp()
#define putsi(x) putnum(x),putendl()
#define putsii(x,y) puti(x),putnum(y),putendl()
#define putsiii(x,y,z) putii(x,y),putnum(z),putendl()
inline ll getnum()
{
	register ll r=0;register bool ng=0;register char c;c=getchar();
	while(c!='-'&&(c<'0'||c>'9'))c=getchar();
	if(c=='-')ng=1,c=getchar();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=getchar();
	if(ng)r=-r;return r;
}
template <class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline void putsp(){putchar(' ');}
inline void putendl(){putchar('\n');}
inline char mygetchar(){register char c=getchar();while(c==' '||c=='\n')c=getchar();return c;}
int head[200111],nxt[5000111],to[5000111],tot=1;
const int nn=80000;
#define nt(v) ((v)<=nn?(v)+nn:(v)-nn)
void addedge(int x,int y)
{
//	cout<<"add:"<<x<<" "<<y<<"  "<<nt(y)<<" "<<nt(x)<<endl;
	nxt[++tot]=head[x];
	head[x]=tot;
	to[tot]=y;
	nxt[++tot]=head[nt(y)];
	head[nt(y)]=tot;
	to[tot]=nt(x);
}
int bs,n,a[10111],b[10111],pa[10111],pb[10111],stot;
pair<int,int> ppos[20111];
const int constlv=16;
int findlw(int v){return lower_bound(ppos+1,ppos+2*n+1,MP(v,0))-ppos;}
void Add(int v,int x,int y,int l,int r,int p=1)
{
	if(x<=l&&r<=y)
	{
		addedge(v,nn+p);
		return;
	}
	int m=l+r>>1;
	if(x<=m)Add(v,x,y,l,m,p<<1);
	if(m<y)Add(v,x,y,m+1,r,p<<1|1);
}
void add(int v,int x,int y)
{
	if(x>y)return;
	Add(v,x,y,1,1<<(constlv-1));
}

int dfn[200111],low[200111],dfntot,g[200111],gtot,st[200111],sttot;
bool live[200111];
void dfs(int x)
{
	dfn[x]=++dfntot;low[x]=dfn[x];
	live[x]=1;
	st[sttot++]=x;
	for(int i=head[x];i;i=nxt[i])
	{
		if(live[to[i]])
		{
			low[x]=min(low[x],dfn[to[i]]);
		}
		else if(!dfn[to[i]])
		{
			dfs(to[i]);
			low[x]=min(low[x],low[to[i]]);
		}
	}
	if(dfn[x]==low[x])
	{
		gtot++;
		while(st[sttot]!=x)
		{
			sttot--;
			g[st[sttot]]=gtot;
			live[st[sttot]]=0;
		}
	}
}
bool check2sat()
{
	dfntot=0;
	memset(dfn,0,sizeof(dfn));
	sttot=0;
	gtot=0;
//	dfs(8);
	for(int i=1;i<=stot;i++)
	{
		if(!dfn[i])
		{
			dfs(i);
		}
		if(!dfn[i+nn])
		{
			dfs(i+nn);
		}
	}
//	for(int i=1;i<=stot;i++)cout<<g[i]<<" ";cout<<endl;
//	for(int i=1;i<=stot;i++)cout<<g[nn+i]<<" ";cout<<endl;
	for(int i=1;i<=stot;i++)
	{
		if(g[i]==g[i+nn])return false;
	}
	return true;
}
bool f[200111];
void solve2sat()
{
	check2sat();
	for(int i=1;i<=nn;i++)
	{
		if(g[i]>g[i+nn])
		{
			f[i]=1;
		}
	}
}

bool solve(int d)
{
	gtot=0;
	tot=1;
	memset(head,0,sizeof(head));
//	cout<<"solve:"<<d<<endl;
	for(int i=2;i<=stot;i++)
	{
		addedge(i,i>>1);
	}
	for(int i=1;i<=n;i++)
	{
		addedge(bs+pa[i],bs+pb[i]+nn);
		addedge(bs+pa[i]+nn,bs+pb[i]);
	}
	for(int i=1;i<=2*n;i++)
	{
		int x=ppos[i].FF;
		add(bs+i,findlw(x-d),i-1);
		add(bs+i,i+1,findlw(x+d+1)-1);
	}
	return check2sat();
}

int main()
{
	stot=(1<<constlv)-1;
	bs=(1<<(constlv-1))-1;
	geti(n);
	for(int i=1;i<=n;i++)
	{
		getii(a[i],b[i]);
		ppos[i]=MP(a[i],i);
		ppos[i+n]=MP(b[i],n+i);
	}
	sort(ppos+1,ppos+n*2+1);
	for(int i=1;i<=2*n;i++)
	{
		if(ppos[i].SS<=n)pa[ppos[i].SS]=i;
		else pb[ppos[i].SS-n]=i;
	}
	
	int l=0,r=1000000000;
//	solve(100);
//	return 0;
	while(l<=r)
	{
		int m=l+r>>1;
		if(solve(m))l=m+1;
		else r=m-1;
//		return 0;
	}
	cout<<l<<endl;
	return 0;
}

Submission Info

Judge Result