Submission #9134616

---

Source Code Expand

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

#define L first
#define R second
typedef pair<int, int> pii;
const int N = 1e5 + 100;

int n, ll[N], lr[N], rl[N], rr[N];
pii p[N];

int f(int l, int r) {
	return max(0, r - l);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p[i].L >> p[i].R;
		p[i].R++;
	}
	sort(p, p + n, [](pii a, pii b) {
		return pii(a.L, -a.R) < pii(b.L, -b.R);
	});
	assert(p[n - 2].L != p[n - 1].L);
	rl[0] = p[0].R;
	for (int i = 1; i < n; i++)
		rl[i] = min(rl[i - 1], p[i].R);

	ll[0] = p[0].L;
	for (int i = 1; i < n; i++)
		ll[i] = max(ll[i - 1], p[i].L);

	rr[n - 1] = p[n - 1].R;
	for (int i = n - 2; ~i; i--)
		rr[i] = min(rr[i + 1], p[i].R);

	lr[n - 1] = p[n - 1].L;
	for (int i = n - 2; ~i; i--)
		lr[i] = max(lr[i + 1], p[i].L);

	int ans = 0;
	for (int i = 0; i < n - 1; i++)
		ans = max(ans, f(ll[i], rl[i]) + f(lr[i + 1], rr[i + 1]));
	for (int i = 1; i < n - 1; i++)
		ans = max(ans, f(max(ll[i - 1], lr[i + 1]), min(rl[i - 1], rr[i + 1])));
	
	cout << ans;
}

Submission Info

Judge Result