Language: C++

#include <bits/stdc++.h>

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = 1'000'000'000'000'007ll;
const llong mod = 1e9+7;

struct data {
	llong L;
	llong R;

	data() = default;
	data(llong L, llong R) :
		L(L),
		R(R)
	{}

	bool operator<(const data &ri) const {
		// return R - L < ri.R - ri.L;
		return R == ri.R ?
			L < ri.L :
			R < ri.R;
	}
};

llong N;
vector<data> tasks;

llong score(llong mid) {
	data d1(-inf, inf), d2(-inf, inf);

	for (auto &task: tasks) {
		if (task.R < mid) {
			d1.L = max(d1.L, task.L);
			d1.R = min(d1.R, task.R);
		} else {
			d2.L = max(d2.L, task.L);
			d2.R = min(d2.R, task.R);
		}
	}

	if (d1.R == inf || d2.R == inf) return -1;
	return max(0ll, d1.R - d1.L + 1) + max(0ll, d2.R - d2.L + 1);
}

int main() {
	vector<llong> pos;

	cin >> N;
	tasks.resize(N);
	for (auto &task: tasks) {
		cin >> task.L >> task.R;
		pos.push_back(task.R);
	}
	pos.push_back(0);
	pos.push_back(inf);

	sort(ALL(tasks));
	sort(ALL(pos));

	llong left = 0, right = pos.size()-1;
	llong lmid, rmid;
	while (lmid = (left * 2 + right) / 3, rmid = (left + right * 2) / 3, right - left > 1000) {
// cerr << left << " " << right << endl;
		llong lscore = score(pos[lmid]);
		llong rscore = score(pos[rmid]);

		if (lmid > rmid) {
			right = rmid;
		} else {
			left = lmid;
		}
	}

	llong ret = 0;
	for (llong &&i = max(0ll, left - 1000); i <= min((llong)(pos.size()-1), right + 1000); ++i) {
		ret = max(ret, score(pos[i]));
	}
	for (auto &task: tasks) {
		ret = max(ret, task.R - task.L + 1);
	}

	cout << ret << endl;

	return 0;
}


/*

片方で残す区間を決め打ったとき、被覆する区間はすべて使用する (もう片方が少ない方がよい) 被覆しない区間はもう片方になる
左右に分けるやつな気がしてきた

ある点より終点が左のやつ、右のやつにわけて三分探索
またぐ区間はどうしよう

*/

Compiler output:
a.cc:32:12: error: template argument 1 is invalid
   32 | vector<data> tasks;
      |            ^
a.cc:32:12: error: template argument 2 is invalid
a.cc: In function 'llong score(llong)':
a.cc:35:9: error: reference to 'data' is ambiguous
   35 |         data d1(-inf, inf), d2(-inf, inf);
      |         ^~~~
In file included from /usr/include/c++/14/string:53,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/bits/range_access.h:344:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
  344 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:334:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  334 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:323:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  323 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:312:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  312 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
a.cc:13:8: note:                 'struct data'
   13 | struct data {
      |        ^~~~
a.cc:37:26: error: 'begin' was not declared in this scope
   37 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:37:26: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:166:
/usr/include/c++/14/valarray:1238:5: note:   'std::begin'
 1238 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
In file included from /usr/include/c++/14/filesystem:53,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:200:
/usr/include/c++/14/bits/fs_dir.h:608:3: note:   'std::filesystem::__cxx11::begin'
  608 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
a.cc:37:26: error: 'end' was not declared in this scope
   37 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:37:26: note: suggested alternatives:
/usr/include/c++/14/valarray:1265:5: note:   'std::end'
 1265 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
/usr/include/c++/14/bits/fs_dir.h:613:3: note:   'std::filesystem::__cxx11::end'
  613 |   end(recursive_directory_iterator) noexcept
      |   ^~~
a.cc:39:25: error: 'd1' was not declared in this scope; did you mean 'y1'?
   39 |                         d1.L = max(d1.L, task.L);
      |                         ^~
      |                         y1
a.cc:42:25: error: 'd2' was not declared in this scope
   42 |                         d2.L = max(d2.L, task.L);
      |                         ^~
a.cc:47:13: error: 'd1' was not declared in this scope; did you mean 'y1'?
   47 |         if (d1.R == inf || d2.R == inf) return -1;
      |             ^~
      |             y1
a.cc:47:28: error: 'd2' was not declared in this scope
   47 |         if (d1.R == inf || d2.R == inf) return -1;
      |                            ^~
a.cc:48:25: error: 'd1' was not declared in this scope; did you mean 'y1'?
   48 |         return max(0ll, d1.R - d1.L + 1) + max(0ll, d2.R - d2.L + 1);
      |                         ^~
      |                         y1
a.cc:48:53: error: 'd2' was not declared in this scope
   48 |         return max(0ll, d1.R - d1.L + 1) + max(0ll, d2.R - d2.L + 1);
      |                                                     ^~
a.cc: In function 'int main()':
a.cc:55:15: error: request for member 'resize' in 'tasks', which is of non-class type 'int'
   55 |         tasks.resize(N);
      |               ^~~~~~
a.cc:56:26: error: 'begin' was not declared in this scope
   56 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:56:26: note: suggested alternatives:
/usr/include/c++/14/valarray:1238:5: note:   'std::begin'
 1238 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
/usr/include/c++/14/bits/fs_dir.h:608:3: note:   'std::filesystem::__cxx11::begin'
  608 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
a.cc:56:26: error: 'end' was not declared in this scope
   56 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:56:26: note: suggested alternatives:
/usr/include/c++/14/valarray:1265:5: note:   'std::end'
 1265 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
/usr/include/c++/14/bits/fs_dir.h:613:3: note:   'std::filesystem::__cxx11::end'
  613 |   end(recursive_directory_iterator) noexcept
      |   ^~~
a.cc:8:18: error: request for member 'begin' in 'tasks', which is of non-class type 'int'
    8 | #define ALL(x) x.begin(), x.end()
      |                  ^~~~~
a.cc:63:14: note: in expansion of macro 'ALL'
   63 |         sort(ALL(tasks));
      |              ^~~
a.cc:8:29: error: request for member 'end' in 'tasks', which is of non-class type 'int'
    8 | #define ALL(x) x.begin(), x.end()
      |                             ^~~
a.cc:63:14: note: in expansion of macro 'ALL'
   63 |         sort(ALL(tasks));
      |              ^~~
a.cc:81:29: error: cannot bind rvalue reference of type 'llong&&' {aka 'long long int&&'} to lvalue of type 'const long long int'
   81 |         for (llong &&i = max(0ll, left - 1000); i <= min((llong)(pos.size()-1), right + 1000); ++i) {
      |                          ~~~^~~~~~~~~~~~~~~~~~
a.cc:84:26: error: 'begin' was not declared in this scope
   84 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:84:26: note: suggested alternatives:
/usr/include/c++/14/valarray:1238:5: note:   'std::begin'
 1238 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
/usr/include/c++/14/bits/fs_dir.h:608:3: note:   'std::filesystem::__cxx11::begin'
  608 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
a.cc:84:26: error: 'end' was not declared in this scope
   84 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:84:26: note: suggested alternatives:
/usr/include/c++/14/valarray:1265:5: note:   'std::end'
 1265 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
/usr/include/c++/14/bits/fs_dir.h:613:3: note:   'std::filesystem::__cxx11::end'
  613 |   end(recursive_directory_iterator) noexcept
      |   ^~~