Language: C++

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}
pii Dir[8] = { //移動
	{ 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 },
	{ 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 }
};
class Graph {
public:
	int vn;
	int sumcost = 0;
	vector<vector<pii>> g;

	Graph(int n) {
		vn = n;
		g.resize(n);
	}
	virtual void con(int a, int b, int w) = 0;
	int getWeight(int f, int t) {
		auto itr = lower_bound(ALL(g[f]), make_pair(t, INT_MIN));
		if (itr != g[f].end())
			return itr->second;
		return INT_MIN;
	}
	int Costsum() {
		return sumcost;
	}
};

class BiDGraph : public Graph {//無向
public:
	BiDGraph(int n) : Graph(n) {}

	void con(int a, int b, int w = 1) {
		g[a].push_back({ b,w });
		g[b].push_back({ a, w });
		sumcost++;
	}
};
class DGraph : public Graph {//有向
public:
	DGraph(int n) : Graph(n) {}
	void con(int a, int b, int w = 1) {
		g[a].push_back({ b,w });
		sumcost++;
	}
};

void SCC(DGraph& g, vector<int>& scc) {
	vector<int>  orb(g.vn, -1);
	scc.resize(g.vn, -1);
	int cc = 0;
	int k = 0;
	vector<bool> used(g.vn);
	stack<int> st;
	function<int(int)> dfs = [&](int cur) {
		int low = orb[cur] = ++k;
		st.push(cur);
		used[cur] = 1;
		for (auto itr : g.g[cur]) {
			if (orb[itr.first] == -1)
				low = min(low, dfs(itr.first));
			else if (used[itr.first])
				low = min(low, orb[itr.first]);
		}
		if (low == orb[cur]) {
			while (1) {
				int cp = st.top(); st.pop();
				used[cp] = 0;
				scc[cp] = cc;
				if (cp == cur)
					break;
			}
			cc++;
		}
		return low;
	};
	REP(i, g.vn)
		if (orb[i] < 0)
			dfs(i);
}

bool TWO_SAT(int n, vector<pii> clause) {//否定は-, 1-indexed
	DGraph g(n * 2);
	for (auto itr : clause) {
		int a = (itr.first < 0 ? -itr.first+n : itr.first)-1, b = (itr.second < 0 ? -itr.second+ n : itr.second)-1;
		g.con(a + (a>=n?-n:n),b);
		g.con(b + (b >= n ? -n : n),a);
	}
	vector<int> scc;
	SCC(g, scc);

	REP(i, n) {
		if (scc[i] == scc[i + n]) {
			return 0;
		}
	}

	return 1;
}

signed main() {
	int n;
	scanf("%d", &n);
	vector<pii> flag(n, {-1,-1});
	vector<pii> ff(n*2);
	REP(i, n) {
		int a, b;
		scanf("%d %d", &a, &b);
		ff[i*2] = { a,i }; ff[i*2+1] = { b,i };
	}
	sort(ALL(ff));
	REP(i, 2 * n) {
		if(flag[ff[i].second].first!= -1)
			flag[ff[i].second].second = i;
		else
			flag[ff[i].second].first = i;
	}
	int l = 0, r = ff[n*2-1].first-ff[0].second+1; 

	vector<pii> clause;
	REP(i, n) {
		clause.push_back({ 1 + flag[i].first,1 + flag[i].second });
		clause.push_back({ -(1 + flag[i].first),-(1 + flag[i].second) });
	}
	int bm = -1;
	while (1) {
		int mid = (l + r) / 2;

		//clause.reserve(n*n/2);
		if (bm < mid) {
			REP(i, n * 2) {
				rep(j, max(i+1,upper_bound(ALL(ff) ,MP(ff[i].first + bm,0)) - ff.begin()), n * 2) {
					if (ff[j].first - ff[i].first >= mid)
						break;
					if (ff[i].second != ff[j].second)
						clause.push_back({ -(i + 1),-(j + 1) });
				}
			}
		}
		else {
			rep(i, n*2,clause.size()) {
				if (abs(ff[abs(clause[i].second)-1].first - ff[abs(clause[i].first)-1].second) >= mid) {
					clause.erase(clause.begin() + i);
				}
			}
		}
		if (TWO_SAT(2 * n, clause)) {
			l = mid;
		}
		else
			r = mid;

		if (r - l <= 1) {
			printf("%d\n", l);
			break;
		}
		bm = mid;
	}

	return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:177:43: error: no matching function for call to 'max(int, __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type)'
  177 |                                 rep(j, max(i+1,upper_bound(ALL(ff) ,MP(ff[i].first + bm,0)) - ff.begin()), n * 2) {
      |                                        ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:18:33: note: in definition of macro 'rep'
   18 | #define rep(i,s,n) for(int i = (s); (n) > i; i++)
      |                                 ^
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:177:43: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'})
  177 |                                 rep(j, max(i+1,upper_bound(ALL(ff) ,MP(ff[i].first + bm,0)) - ff.begin()), n * 2) {
      |                                        ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:18:33: note: in definition of macro 'rep'
   18 | #define rep(i,s,n) for(int i = (s); (n) > i; i++)
      |                                 ^
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:7:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:177:43: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  177 |                                 rep(j, max(i+1,upper_bound(ALL(ff) ,MP(ff[i].first + bm,0)) - ff.begin()), n * 2) {
      |                                        ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:18:33: note: in definition of macro 'rep'
   18 | #define rep(i,s,n) for(int i = (s); (n) > i; i++)
      |                                 ^