Submission #1793557

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

const int MAXN = 10 * 10000 + 100;

typedef pair<int, int> pii;

int n;
pii s[MAXN];
vector<int> edg[MAXN];
int tot, N, pos[MAXN];
int dfn[MAXN], low[MAXN], bel[MAXN], totw;
bool inst[MAXN];
stack<int> sta;

void init()
{
	tot = 2 * n;
	N = totw = 0;
	for(int i = 0; i < MAXN; i++)
		edg[i].clear();
	memset(dfn, 0, sizeof(dfn));
}

void add_edg(int x, int y)
{
	// cerr << "E" << x << ' ' << y << endl;
	edg[x].push_back(y);
}

void build()
{
	for(N = 1; N < 2 * n + 2; N <<= 1);
	// cerr << N << endl;
	for(int i = 1; i < N + N; i++)
		pos[i] = tot++;
	for(int i = 1; i < N; i++)
		add_edg(pos[i], pos[2 * i]), add_edg(pos[i], pos[2 * i + 1]);
	for(int i = 0; i < 2 * n; i++)
		add_edg(pos[N + i + 1], s[i].second ^ 1);
}

void link(int l, int r, int id) // index from zero
{
	if(l > r) return ;
	l += 1, r += 1;
	// cerr << l << ' ' << r << endl;
	for(l += N - 1, r += N + 1; (l ^ r) != 1; l >>= 1, r >>= 1)
	{
		if(~l & 1) add_edg(id, pos[l ^ 1]);
		if(r & 1) add_edg(id, pos[r ^ 1]);
	}
}

void tarjan(int x)
{
	dfn[x] = low[x] = ++totw;
	sta.push(x), inst[x] = true;
	for(int i = 0; i < edg[x].size(); i++)
	{
		int y = edg[x][i];
		if(!dfn[y])
			tarjan(y), low[x] = min(low[x], low[y]);
		else if(inst[y])
			low[x] = min(low[x], dfn[y]);
	}
	if(low[x] == dfn[x])
	{
		int y;
		do
		{
			y = sta.top();
			sta.pop(), inst[y] = false;
			bel[y] = x;
		}
		while(y != x);
	}
}

bool check(int k)
{
	init();
	build();
	int lp = 0, rp = 0;
	for(int i = 0; i < 2 * n; i++)
	{
		while(lp < 2 * n && s[lp].first <= s[i].first - k)
			lp++;
		while(rp < 2 * n && s[rp].first < s[i].first + k)
			rp++;
		// cerr << i << ' ' << lp << ' ' << rp << endl;
		link(lp, i - 1, s[i].second);
		link(i + 1, rp - 1, s[i].second);
	}
	for(int i = 0; i < tot; i++)
		if(!dfn[i])
			tarjan(i);
	// for(int i = 0; i < n; i++)
	// 	cerr << "!" << bel[2 * i] << ' ' << bel[2 * i + 1] << endl;
	for(int i = 0; i < n; i++)
		if(bel[2 * i] == bel[2 * i + 1])
			return false;
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);

	cin >> n;
	for(int i = 0; i <= n - 1; i++)
	{
		cin >> s[2 * i].first >> s[2 * i + 1].first;
		s[2 * i].second = 2 * i, s[2 * i + 1].second = 2 * i + 1;
	}
	sort(s, s + 2 * n);

	// cerr << check(10) << endl;

	int l = 0, r = 1000000000;
	while(l < r)
	{
		int mid = (l + r + 1) / 2;
		if(check(mid))
			l = mid;
		else
			r = mid - 1;
	}
	cout << l << endl;


	return 0;
}

Submission Info

Judge Result