Submission #1831278

---

Source Code Expand

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

const int N = 200005;
const int inf = 1e9;

int n, tot, MAX;
pair<int,int> z[N];
vector<int> G[N * 2];
int pos_seg[N];
int lst[N];

void add(int u, int v) {
	G[-v + N].push_back(u + N);
	G[-u + N].push_back(v + N);
}

// SEGMENT TREE
#define mid ((l + r) >> 1)
void build(int v, int l, int r) {
	if (l > r) return;
	if (l == r) {
		int pos = z[l].second;
		pos_seg[l] = v;
		if (lst[pos]) add(-v, -lst[pos]), add(v, lst[pos]); else lst[pos] = v;
		MAX = max(MAX, v);
		return;
	}
	build(v << 1, l, mid); build(v << 1 | 1, mid + 1, r);
	add(v, -(v << 1));
	add(v, -(v << 1 | 1));
}

void join(int pos, int v, int l, int r, int L, int R) {
	if (l > r || R < l || L > r) return;
	if (L <= l && r <= R) { add(-pos, -v); return; }
	join(pos, v << 1, l, mid, L, R); join(pos, v << 1 | 1, mid + 1, r, L, R);
}
#undef mid
// ------------------

// TWO-SAT
int color[N * 2];
int low[N * 2], num[N * 2], step;
bool invalid;

void setColor(int u, int c) { // FALSE = 1, TRUE = 2
	u -= N;
	if (color[u + N] == 3-c) invalid = true; else color[u + N] = c;
	if (color[-u + N] == c) invalid = true; else color[-u + N] = 3-c;
}

stack<int> st;
void dfs(int u) {
	low[u] = num[u] = ++step; st.push(u);
	for (int i = 0; i < G[u].size(); ++i) {
		int v = G[u][i];
		if (num[v]) low[u] = min(low[u], num[v]);
		else dfs(v), low[u] = min(low[u], low[v]);
		if (color[v] == 1) setColor(u, 1); // FALSE
	}

	if (low[u] == num[u]) {
		int v = 0;
		if (!color[u]) setColor(u, 2); // TRUE
		do {
			v = st.top(); st.pop();
			setColor(v, color[u]);
			low[v] = num[v] = inf;
		} while(v != u);
	}
}

bool check(int d) {
	// reset
	for (int i = 1; i <= n; ++i) lst[i] = 0;
	for (int i = 1; i <= MAX; ++i) G[i + N].clear(), color[i + N] = 0, low[i + N] = num[i + N] = 0;
	for (int i = 1; i <= MAX; ++i) G[-i + N].clear(), color[-i + N] = 0, low[-i + N] = num[-i + N] = 0;
	step = 0;
	invalid = false;
	build(1, 1, tot);

	// solve
	int ptr = 1;
	for (int i = 1; i <= tot; ++i) {
		while(ptr <= i && z[i].first - z[ptr].first >= d) ++ptr; 
		join(pos_seg[i], 1, 1, tot, ptr, i - 1);
		//cerr << i << " [" << ptr << "," << i-1 << "]" << endl;
	}
	ptr = tot;
	for (int i = tot; i >= 1; --i) {
		while(ptr >= i && z[ptr].first - z[i].first >= d) --ptr;
		join(pos_seg[i], 1, 1, tot, i + 1, ptr);
		//cerr << i << " [" << i+1 << "," << ptr << "]" << endl;
	}

	for (int i = 1; i <= MAX; ++i) if (!num[i + N]) dfs(i + N);
	for (int i = 1; i <= MAX; ++i) if (!num[-i + N]) dfs(-i + N);

	return !invalid;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x, y; cin >> x >> y;
		z[++tot] = make_pair(x, i);
		z[++tot] = make_pair(y, i);
	}
	sort(z + 1, z + tot + 1);
	build(1, 1, tot);
	
	int l = 0, r = 1e9;
	while(l < r) {
		int mid = ((l + r + 1) >> 1);
		if (check(mid)) l = mid; else r = mid - 1;
	}
	cout << l << endl;
}

Submission Info

Judge Result