为什么 up(i,0,2*tot) stk[i]=vis[i]=gp[i]=tag[i]=0, F[i].clear(), G[i].clear(); 要写两倍 $tot$ 才能过 /yiw

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define pb push_back

using namespace std;

const int N=2000005;

int n, tot, tr[N], tag[N];
int stk[N], top, gp[N], cnt, vis[N], tmp;
vector<int> F[N], G[N];
struct node {
	int x, id;
	bool operator<(const node &rhs) const { return x<rhs.x; }
} a[N];

void build(int p=1,int s=1,int e=2*n) {
	tr[p]=++tot;
	if(s==e) return;
	int mid=(s+e)>>1;
	build(ls(p),s,mid), build(rs(p),mid+1,e);
}

void link(int x,int l,int r,int p=1,int s=1,int e=2*n) {
	if(l<=s&&e<=r) {
		if(!tag[p]) {
			up(i,s,e) {
				int ch=(a[i].id&1)?+1:-1;
				F[tr[p]].pb(a[i].id+ch);
			}
			tag[p]=1;
		}
		F[x].pb(tr[p]);
		return;
	}
	int mid=(s+e)>>1;
	if(l<=mid) link(x,l,r,ls(p),s,mid);
	if(r>mid) link(x,l,r,rs(p),mid+1,e);
}

void dfs(int x) {
	vis[x]=1;
	for(int y:F[x]) if(!vis[y]) dfs(y);
	stk[++top]=x;
}

void stain(int x) {
	for(int y:G[x]) if(!gp[y]) gp[y]=cnt, stain(y);
}

bool check(int dis) {
	cnt=top=0;
	up(i,0,2*tot) stk[i]=vis[i]=gp[i]=tag[i]=0, F[i].clear(), G[i].clear();
	int l=1, r=1;
	up(i,1,2*n) {
		while(r<2*n&&a[r+1].x-a[i].x<dis) ++r;
		while(a[i].x-a[l].x>=dis) ++l;
		if(l<i) link(a[i].id,l,i-1);
		if(i<r) link(a[i].id,i+1,r);
	}
	up(x,1,tot) for(int y:F[x]) G[y].pb(x);
	up(i,1,tot) if(!vis[i]) dfs(i);
	dn(i,tot,1) if(!gp[tmp=stk[i]]) gp[tmp]=++cnt, stain(tmp);
	for(int i=1; i<=2*n; i+=2) if(gp[i]==gp[i+1]) return 0;
	return 1;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	up(i,1,n) {
		int X, Y;
		cin >> X >> Y;
		++tot, a[tot]=(node){X,tot};
		++tot, a[tot]=(node){Y,tot};
	}
	if(n==1) { cout << 0; return 0; } 
	sort(a+1,a+1+tot);
	build();
	int l=0, r=1e9, Ans;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) Ans=mid, l=mid+1;
		else r=mid-1;
	}
	cout << Ans << '\n';
	return 0;
}