Language: C++

#include <bits/stdc++.h>
#define RI register int
#define lc (x << 1)
#define rc (x << 1 | 1)

using namespace std;

int const MAXN = 1e8 + 5;
int MaxNode = 0, n, _2n;
struct Edges { int to, next; } e[MAXN * 2];
int head[MAXN], tot;
int Dfn[MAXN], Col[MAXN], col, Low[MAXN], cnt, stk[MAXN], top, vis[MAXN];
struct nodes { int x, y; } a[MAXN];
struct Nodes { int x, id; } t[MAXN];
inline bool cmp(Nodes x, Nodes y) { return x.x < y.x; }

inline void addedge(int from, int to) {
  e[++tot] = (Edges){to, head[from]};
  head[from] = tot;
}

void Get_MaxNode(int x, int l, int r) {
  MaxNode = max(MaxNode, x);
  if (l == r) return;
  int mid = (l + r) >> 1;
  Get_MaxNode(lc, l, mid);
  Get_MaxNode(rc, mid + 1, r);
}

void Build(int x, int l, int r, int opt) {
  if (!opt) addedge(x, x + MaxNode);
  if (l == r) return;
  if (!opt) addedge(x, lc), addedge(x, rc);
  else addedge(lc + MaxNode, x + MaxNode), addedge(rc + MaxNode, x + MaxNode);
  int mid = (l + r) >> 1;
  Build(lc, l, mid, opt);
  Build(rc, mid + 1, r, opt);
}

int Get(int x, int l, int r, int to) {
  if (l == r) return x;
  int mid = (l + r) >> 1;
  if (to <= mid) return Get(lc, l, mid, to);
  else return Get(rc, mid + 1, r, to);
}
void Link(int x, int l, int r, int i, int j, int node) {
  if (i > j) return;
  if (l == r) return addedge(x + MaxNode, node);
  int mid = (l + r) >> 1;
  if (i <= mid) Link(lc, l, mid, i, j, node);
  if (j > mid) Link(rc, mid + 1, r, i, j, node);
}

void Tarjan(int k) {
  Low[k] = Dfn[k] = ++cnt;
  vis[k] = stk[++top] = k;
  for (RI i = head[k]; i; i = e[i].next)
      if (!Dfn[e[i].to]) {
        Tarjan(e[i].to);
        Low[k] = min(Low[k], Low[e[i].to]);
      }
      else if (vis[e[i].to]) Low[k] = min(Low[k], Dfn[e[i].to]);
  if (Dfn[k] == Low[k]) {
    ++col;
    while (stk[top] != k) Col[stk[top]] = col, vis[stk[top]] = 0, --top;
    Col[stk[top]] = col, vis[stk[top]] = 0, --top;
  }
}

bool Check(int k) {
  for (RI i = 1; i <= MaxNode * 2; ++i)
    head[i] = Dfn[i] = Low[i] = Col[i] = 0;
  tot = cnt = col = top = 0;
  Build(1, 1, _2n, 0);
  Build(1, 1, _2n, 1);
  for (RI i = 1; i <= _2n; ++i) {
    int l = 1, r = i - 1, mid, ll = i;
    while (l <= r) {
      mid = (l + r) >> 1;
      if (t[i].x - t[mid].x >= k) l = mid + 1;
      else ll = mid, r = mid - 1;
    }
    l = i + 1, r = _2n; int rr = i;
    while (l <= r) {
      mid = (l + r) >> 1;
      if (t[mid].x - t[i].x >= k) r = mid - 1;
      else rr = mid, l = mid + 1;
    }
    Link(1, 1, _2n, ll, i - 1, Get(1, 1, _2n, a[t[i].id].x == i ? a[t[i].id].y : a[t[i].id].x));
    Link(1, 1, _2n, i + 1, rr, Get(1, 1, _2n, a[t[i].id].x == i ? a[t[i].id].y : a[t[i].id].x));
  }
  for (RI i = 1; i <= 2 * MaxNode; ++i)
    if (!Dfn[i]) Tarjan(i);
  for (RI i = 1; i <= n; ++i)
    if (Col[Get(1, 1, _2n, a[i].x)] == Col[Get(1, 1, _2n, a[i].y)])
      return 0;
  return 1;
}

int main() {
  freopen("a.in", "r", stdin);
  freopen("a.out", "w", stdout);
  ios :: sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n; _2n = n + n;
  Get_MaxNode(1, 1, _2n);
  for (RI i = 1; i <= n; ++i)
    cin >> t[i * 2 - 1].x >> t[i * 2].x, t[i * 2 - 1].id = t[i * 2].id = i;
  sort(t + 1, t + 1 + _2n, cmp);
  for (RI i = 1; i <= _2n; ++i) {
    if (!a[t[i].id].x) a[t[i].id].x = i;
    else a[t[i].id].y = i;
  }
  int l = 1, r = 1e9, mid, ans = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (Check(mid)) ans = mid, l = mid + 1;
    else r = mid - 1;
  }
  cout << ans << endl;
  return 0;
}


Compiler output:
a.cc: In function 'void Tarjan(int)':
a.cc:57:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   57 |   for (RI i = head[k]; i; i = e[i].next)
      |           ^
a.cc: In function 'bool Check(int)':
a.cc:71:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   71 |   for (RI i = 1; i <= MaxNode * 2; ++i)
      |           ^
a.cc:76:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   76 |   for (RI i = 1; i <= _2n; ++i) {
      |           ^
a.cc:92:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   92 |   for (RI i = 1; i <= 2 * MaxNode; ++i)
      |           ^
a.cc:94:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   94 |   for (RI i = 1; i <= n; ++i)
      |           ^
a.cc: In function 'int main()':
a.cc:107:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  107 |   for (RI i = 1; i <= n; ++i)
      |           ^
a.cc:110:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  110 |   for (RI i = 1; i <= _2n; ++i) {
      |           ^
/tmp/ccwhrkuc.o: in function `Tarjan(int)':
a.cc:(.text+0x2ae): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x2b7): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x2bd): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x301): relocation truncated to fit: R_X86_64_PC32 against symbol `Low' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x30d): relocation truncated to fit: R_X86_64_PC32 against symbol `top' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x316): relocation truncated to fit: R_X86_64_PC32 against symbol `top' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x31c): relocation truncated to fit: R_X86_64_PC32 against symbol `top' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x32e): relocation truncated to fit: R_X86_64_PC32 against symbol `stk' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x342): relocation truncated to fit: R_X86_64_PC32 against symbol `stk' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x35a): relocation truncated to fit: R_X86_64_PC32 against symbol `vis' defined in .bss section in /tmp/ccwhrkuc.o
a.cc:(.text+0x3ec): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status