Submission #1119691

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a));

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const long double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 100005;

vector<PII> f;

VI g[MAX];
VI gr[MAX];
int n;

void add_edge(int a,int b)
{
	g[a].PB(b);
	gr[b].PB(a);
}


struct RMQ
{
	int n;
	int sh;
	int mx;


	void init(int v,int tl,int tr)
	{
		if(tl == tr)
		{
			mx = max(mx,sh+v+1);
			add_edge(sh+v,f[tl].second);
			return;
		}

		int tm = (tl+tr)/2;
		add_edge(v + sh, 2*v + sh);
		add_edge(v + sh, 2*v+1 + sh);
		init(v*2,tl,tm);
		init(v*2+1,tm+1,tr);
	}

	void init(int n,int sh)
	{
		this->n = n;
		this->sh = sh ;
		mx = 0;
		init(1,0,this->n-1);
	}
	void add(int v,int tl,int tr,int l,int r,int x)
	{
		if(l>r)return;
		if(l==tl && r == tr)
		{
			add_edge(x,v+sh);
			return;
		}

		int tm = (tl+tr)/2;
		add(v*2,tl,tm,l,min(r,tm),x);
		add(v*2+1,tm+1,tr,max(l,tm+1),r,x);
	}

	void add(int l,int r,int x)
	{
		add(1,0,n-1,l,r,x);
	}
} T;


bool us[MAX];
int cInd[MAX];
VI tops;

void dfs1 (int v) {
	us[v] = true;
	FOR(i,0,SZ(g[v]))
		if (!us[ g[v][i] ])
			dfs1 (g[v][i]);
	tops.push_back (v);
}

void dfs2 (int v,int ind) {
	us[v] = true;
	cInd[v] = ind;
	FOR(i,0,SZ(gr[v]))
		if (!us[ gr[v][i] ])
			dfs2 (gr[v][i],ind);
}

int N;
bool ok(int d)
{
	FOR(i,0,N)g[i].clear(),gr[i].clear();
	T.init(2*n,2*n);

	N = T.mx;
	FOR(i,0,SZ(f))
	{
		int nv = f[i].second;
		if(nv<n)nv+=n;
		else nv -= n;

		int ub = upper_bound(ALL(f),MP(f[i].first+d-1,INF))-f.begin()-1;
		T.add(i+1,ub,nv);

		int lb = upper_bound(ALL(f),MP(f[i].first-d,INF))-f.begin();

		T.add(lb,i-1,nv);
	}

	/*FOR(i,0,N)
	{
		cerr<<i<<":"<<endl;
		FOR(j,0,SZ(g[i]))cerr<<g[i][j]<<" ";
		cerr<<endl;
	}*/

	FILL(us,0);
	tops.clear();
	FOR(i,0,N)
	if(!us[i])dfs1(i);

	FILL(us,0);

	reverse(ALL(tops));
	int ind = 0;
	FOR(i,0,N)
	{
		int v=tops[i];
		if(!us[v])dfs2(v,ind++);
	}

	FOR(i,0,n)if(cInd[i]==cInd[i+n])return false;

	return true;

}
int main()
{
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);

	cin>>n;
	FOR(i,0,n)
	{
		int a,b;
		cin>>a>>b;
		f.PB(MP(a,i));
		f.PB(MP(b,i+n));
	}

	sort(ALL(f));

	//cout<<ok(2);
	int l=0,r=1000000001;

	while(l+1<r)
	{
		int x = (l+r)/2;
		if(ok(x))l=x;
		else r=x;
	}

	cout<<l;
}

Submission Info

Judge Result