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;
	}
	bool operator==(const data &an) const {
		return L == an.L && R == an.R;
	}
};

llong N;
vector<data> tasks;

llong score(llong mid, llong id) {
	data d1(-inf, inf), d2(-inf, inf);
	data d3 = d1, d4 = d1;

	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 (task == tasks[id]) {
			d3.L = max(d3.L, task.L);
			d3.R = min(d3.R, task.R);
		} else {
			d4.L = max(d4.L, task.L);
			d4.R = min(d4.R, task.R);
		}
	}

	llong a = 0, b = 0;
	if (d1.R != inf && d2.R != inf)
		a = max(0ll, d1.R - d1.L + 1) + max(0ll, d2.R - d2.L + 1);
	if (d3.R != inf && d4.R != inf)
		b = max(0ll, d3.R - d3.L + 1) + max(0ll, d4.R - d4.L + 1);

	return max(a, b);
}

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 >　9000) {
		llong lscore = score(pos[lmid], lmid);
		llong rscore = score(pos[rmid], rmid);

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

	llong ret = 0;
	for (llong i = max(0ll, left - 1000); i <= min((llong)(pos.size()-2), right + 1000); ++i) {
		ret = max(ret, score(pos[i], i));
	}

	cout << ret << endl;

	return 0;
}


/*

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

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

*/

Compiler output:
a.cc:85:92: error: extended character 　 is not valid in an identifier
   85 |         while (lmid = (left * 2 + right) / 3, rmid = (left + right * 2) / 3, right - left >　9000) {
      |                                                                                            ^
a.cc:35:12: error: template argument 1 is invalid
   35 | vector<data> tasks;
      |            ^
a.cc:35:12: error: template argument 2 is invalid
a.cc: In function 'llong score(llong, llong)':
a.cc:38:9: error: reference to 'data' is ambiguous
   38 |         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:39:9: error: reference to 'data' is ambiguous
   39 |         data d3 = d1, d4 = d1;
      |         ^~~~
/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:41:26: error: 'begin' was not declared in this scope
   41 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:41: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:41:26: error: 'end' was not declared in this scope
   41 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:41: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:43:25: error: 'd1' was not declared in this scope; did you mean 'y1'?
   43 |                         d1.L = max(d1.L, task.L);
      |                         ^~
      |                         y1
a.cc:46:25: error: 'd2' was not declared in this scope
   46 |                         d2.L = max(d2.L, task.L);
      |                         ^~
a.cc:50:34: error: invalid types 'int[llong {aka long long int}]' for array subscript
   50 |                 if (task == tasks[id]) {
      |                                  ^
a.cc:51:25: error: 'd3' was not declared in this scope
   51 |                         d3.L = max(d3.L, task.L);
      |                         ^~
a.cc:54:25: error: 'd4' was not declared in this scope
   54 |                         d4.L = max(d4.L, task.L);
      |                         ^~
a.cc:60:13: error: 'd1' was not declared in this scope; did you mean 'y1'?
   60 |         if (d1.R != inf && d2.R != inf)
      |             ^~
      |             y1
a.cc:60:28: error: 'd2' was not declared in this scope
   60 |         if (d1.R != inf && d2.R != inf)
      |                            ^~
a.cc:62:13: error: 'd3' was not declared in this scope
   62 |         if (d3.R != inf && d4.R != inf)
      |             ^~
a.cc:62:28: error: 'd4' was not declared in this scope
   62 |         if (d3.R != inf && d4.R != inf)
      |                            ^~
a.cc: In function 'int main()':
a.cc:72:15: error: request for member 'resize' in 'tasks', which is of non-class type 'int'
   72 |         tasks.resize(N);
      |               ^~~~~~
a.cc:73:26: error: 'begin' was not declared in this scope
   73 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:73: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:73:26: error: 'end' was not declared in this scope
   73 |         for (auto &task: tasks) {
      |                          ^~~~~
a.cc:73: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:80:14: note: in expansion of macro 'ALL'
   80 |         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:80:14: note: in expansion of macro 'ALL'
   80 |         sort(ALL(tasks));
      |              ^~~
a.cc:85:92: error: '\U000030009000' was not declared in this scope
   85 |         while (lmid = (left * 2 + right) / 3, rmid = (left + right * 2) / 3, right - left >　9000) {
      |                                                                                            ^~~~~~