まず単純に比較する事を考えると、これは \(NM\) 個の組について差分を取って比較する必要があり、今回の制約下では最大 \(4\times 10^{10}\) 回行う必要があるためこれは間に合いません。

そこで、まず \(2\) つの数列をソートします。入力された数列や集合について、順序が意味を持たないものについてはとりあえずソートして単調性を付加することによって解きやすくなることがあります。少なくとも入力される個数に対してソートができないことは現状では少なく、元の問題が解けるならばソートした後の入力についても解けるはずなので、そのような場合を考えることによって損をすることは無いです。

さて、ソートした後のものを考えます。 すなわち、 \(A_1\leq A_2\cdots \leq A_N\) , \(B_1\leq B_2\cdots \leq B_M\) が成り立っているとします。このとき、 \(i=1,2,\ldots,N\) について順に \(\lvert A_i-B_j\rvert\) が最小となるような \(j\) を探すことを考えます。 \(A_i\leq B_j\) であるならば任意の \(j< j'\) について \(\lvert A_i-B_j\rvert=B_j-A_i\leq B_{j'}-A_i=\lvert A_i-B_{j'}\rvert\) が成り立つため \(j\) より大きい \(j'\) について試す必要はありません。これで少し減らせた気分がしますが、 \(A_i>B_N\) であるとき、結局すべて試すことになるため、これでは足りません。ここで、逆も使えることが肝要な点です。すなわち、\(B_j\leq A_i<B_{j+1}\) となったとすると、 \(j'\leq j\) については\(\lvert A_{i+1}-B_{j'} \rvert=A_{i+1}-B_{j'}\geq A_{i+1}-B_{j}\geq A_i-B_j=\lvert A_i-B_j\rvert\) より調べる必要がありません。

これをまとめると\(A_1\) と \(B_1\) から始めて次の操作を繰り返せば答えが求まる事が分かります。

• \(\lvert A_i-B_j\rvert\) の値が今までに調べた差分のいずれよりも小さければ暫定的な答えを変更する。
• その後、 \(A_i\) と \(B_j\) を比較する。
• \(A_i> B_j\) ならば \(B_j\) を \(B_{j+1}\) に変えて次の操作を行う。
• \(A_i\leq B_j\)であるならば \(j<j'\) であるような \(j'\) について \(\lvert A_{i}-B_{j'}\rvert\)を調べる必要はない。さらに\(A_{i+1}\) についても \(j'<j\) であるような \(j'\) について \(\lvert A_{i+1}-B_{j'}\rvert\) の値を調べる必要はないため、 \(A_{i+1}\) と \(B_j\) について次の操作を行う。
• \(i>N\) または \(j>M\) となったならば操作を終了する。

さて、この場合の計算量を考えると、操作の度に \(i+j\) の値が \(1\) つずつ増えています。よって操作回数は高々 \(N+M-1\) 回です。各操作は \(O(1)\) で行えるため、この部分については\(O(N+M)\) で行う事ができ、最初のソートとあわせて、\(O(N\log N+M\log M)\) でこの問題は解けました。

C++による実装例:

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

#define N 200010
#define INF 1010000000
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	int n, m;
	int a[N];
	int b[N];
	int ans = INF;
	cin >> n >> m;
	rep(i, n)cin >> a[i];
	rep(i, m)cin >> b[i];
	sort(a, a + n);
	sort(b, b + m);
	int x = 0;
	int y = 0;
	while ((x < n) && (y < m)) {
		ans = min(ans, abs(a[x] - b[y]));
		if (a[x] > b[y])y++;
		else x++;
	}
	cout << ans << endl;

	return 0;
}