Submission #1833901

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define fore(e, u, v) for (int p = e(u), v = e[p].y; p; v = e[p = e[p].nxt].y)
#define ri rd<int>
using namespace std;
const int maxN = 2e4 + 7;
const int maxP = maxN << 2;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

int n, m;
int a[maxN], b[maxN];
struct rec {
	int x, i;
	inline bool operator < (const rec &v) const { return x < v.x; }
}q[maxN];
int dfn[maxP], low[maxP], tdfn;
int col[maxP], cnt;
int stack[maxP], Top, inst[maxP];

struct vec {
	static const int maxE = maxN * 120;
	int g[maxP], te;
	struct edge {int y, nxt;} e[maxE];
	inline void clear() {memset(g, 0, sizeof g); te = 0;}
	inline void push(int x, int y) {e[++te] = (edge){y, g[x]}; g[x] = te;}
	inline void link(int x, int y) {push(x, y), push(y, x);}
	inline int& operator () (int x) {return g[x];}
	inline edge& operator [] (int x) {return e[x];}
};

namespace Seg {

	int rt[2], tot;
	int id[2][maxP];
	int lc[2][maxP], rc[2][maxP];
	vec e;

	void add(int kd, int x, int l, int r, int tl, int tr, int t) {
		if (tl <= l && r <= tr) {
			if (kd == 0) e.push(t, x);
			else e.push(x, t);
			return;
		}
		int mid = (l + r) >> 1;
		if (tl <= mid) add(kd, lc[kd][x], l, mid, tl, tr, t);
		if (mid < tr) add(kd, rc[kd][x], mid+1, r, tl, tr, t);
	}

	int build(int kd, int l, int r) {
		int x = ++ tot;
		if (l == r) {
			id[kd][l] = x;
			return x;
		}
		int mid = (l + r) >> 1;
		lc[kd][x] = build(kd, l, mid);
		rc[kd][x] = build(kd, mid+1, r);
		if (kd == 0) e.push(x, lc[kd][x]), e.push(x, rc[kd][x]);
		else e.push(lc[kd][x], x), e.push(rc[kd][x], x);
		return x;
	}
	
	void init(int n) {
		e.clear();
		tot = 0;
		rt[0] = build(0, 1, n);
		rt[1] = build(1, 1, n);
	}

	void one(int x, int y) {
		e.link(id[0][x], id[1][y]);
		e.link(id[0][y], id[1][x]);
	}

	void both(int l, int r, int x) {
		Seg::add(0, rt[0], 1, m, l, r, id[1][x]);
		Seg::add(1, rt[1], 1, m, l, r, id[0][x]);
	}

	void dfs(int x) {
		dfn[x] = low[x] = ++tdfn;
		stack[++Top] = x;
		inst[x] = 1;
		fore (e, x, y) {
			if (!dfn[y]) {
				dfs(y);
				low[x] = min(low[x], low[y]);
			}
			else if (inst[y]) {
				low[x] = min(low[x], dfn[y]);
			}
		}
		if (low[x] == dfn[x]) {
			++ cnt;
			do {
				col[stack[Top]] = cnt;
				inst[stack[Top]] = 0;
			} while (stack[Top --] != x);
		}
	}

	bool tarjan() {
		tdfn = cnt = 0; memset(dfn, 0, sizeof dfn);
		rep (i, 1, m) if (!dfn[id[0][i]]) dfs(id[0][i]);
		rep (i, 1, m) if (!dfn[id[1][i]]) dfs(id[1][i]);
		rep (i, 1, m) if (col[id[0][i]] == col[id[1][i]]) return 0;
		return 1;
	}
}

bool solve(int d) {
	Seg::init(m);
	rep (i, 1, n) Seg::one(a[i], b[i]);
	for (int i = 1, j = 1; i <= m; ++ i) {
		for (; j <= m && q[i].x - q[j].x >= d; ++ j);
		if (j < i) Seg::both(j, i-1, i);
	}
	return Seg::tarjan();
}

int main() {

	n = ri();
	rep (i, 1, n) q[++m] = (rec){ri(), i}, q[++m] = (rec){ri(), i};
	sort(q+1, q+m+1);
	rep (i, 1, m) if (!a[q[i].i]) a[q[i].i] = i; else b[q[i].i] = i;

	int l = 0, r = 1000000000;
	while (l < r) {
		int mid = (l + r) / 2 + 1;
		if (solve(mid)) l = mid;
		else r = mid - 1;
	}
	printf("%d\n", l);

	return 0;
}

Submission Info

Judge Result