概要
解法 （時間計算量 $\Theta(N\log N\log A)$）
二分探索します．次が $\Theta(N\log N)$ 時間で解ければよいです．
$(A_1, \ldots, A_{3N})$ と $(B_1, \ldots, B_N)$ と $K$ が与えられる．各 $i$ に対して，$A_i, \ldots, A_{i+N-1}$ と $B_1, \ldots, B_N$ の間の完全マッチングであって，各対の差が $K$ 以下であるものが存在するか否かを判定せよ．
なお本問では $A$ に単峰性が仮定されていますが，ここではまだ使いません．
以下，完全マッチングといえばどの対の差も $K$ 以下であるものとします．
まず $i$ を固定したときの判定問題を考えます．これにはソートして貪欲などの単純な解法もありますが，ここでは Hall の定理による特徴づけを考えます．
$(a_1,\ldots,a_N)$ と $(b_1,\ldots,b_N)$ がソートされているとき, これらの間に完全マッチングが存在しないのは，次が成り立つ場合です：
$a_i$ からうまく $n$ 個選んだとき，選んだいずれかの $a_i$ との距離が $K$ 以下であるような $b_j$ の個数が $n-1$ 個以下になる．
このような反例となる $n$ 個の選び方について，各 $a_i$ の近傍は区間で，数える $b_j$ はそれらの区間の和集合です．区間の和集合が $2$ つ以上の連結成分に分かれる場合には，いずれかの成分が反例を与えるため，$a_i$ の近傍となる区間全体は連結であるとしてよいです．このとき，$a_i < a_j < a_k$ であり $a_i, a_k$ を選ぶならば $a_j$ も選ぶとしてよいことが分かります．したがって，$a_l, \ldots, a_r$ というような選び方のみ探索すればよいことが分かります．
各 $a_i$ について，$a_i-K$ 未満の $b_j$ の個数を $x_i$，$a_i+K$ 以下の $b_j$ の個数を $y_i$ とし，$z_i=1$ とすれば，次のような問題に帰着されます：
$(z_l+\cdots+z_r)-(y_r-x_l)\geq 1$ を満たす $(l,r)$ が存在するか判定せよ．
これはセグメント木で扱える形です．区間に対する左辺の最大値の他，$x_l+(z_l+z_{l+1}+\cdots)$ や $(\cdots + z_r)-y_r$ の最大値などを管理します．
判定問題がセグメント木で解ける形になったので，セグメント木の点更新を利用すればすべての $(A_i, \ldots, A_{i+N-1})$ に対する問題が解けます．項 $A_i$ に対応するセグメント木のインデックスは，$i$ ではなく $A_i$ を座圧したものとします．$A$ を座圧しておくと，おおよそ次のような手順になります：
- セグメント木における $A[0], \ldots, A[N-1]$ 番目のノードに適当な値を入れる．
- $A[N+i]$ 番目のノードに値を入れ，$A[i]$ 番目のノードの値を削除（単位元に置き換え）する．
- 適宜，セグメント木の要素の総積を求める．
これで $O(N\log N\log A)$ 時間の解法になります．残念ながら 30 点しかとれませんでした．
解法 （時間計算量 $\Theta(N\log A)$）
入力の特徴を利用して高速化しましょう．
$A$ に単調性があることを利用します．$p_i = \min(A[i], A[N+i])$, $q_i = \max(A[i], A[N+i])$ とすると，$\sum |p_i-p_{i+1}|$ や $\sum |q_i-q_{i+1}|$ は $O(N)$ です．つまり，セグメント木の点更新を行うのですが，その位置のインデックス変化の総和が小さいです．このことを利用しましょう．
列のデータを次の 3 つに分けて管理します：$[0,p_i), [p_i,q_i), [q_i,2N)$．
セグメント木はあきらめて，それぞれの部分を SWAG で管理します．$p_i, q_i$ の変更は，先頭や末尾に対する push, pop で書けます（mo のアルゴリズムの有名な実装と同じようにできる）．$p_i$ や $q_i$ に対する点更新も，先頭に対する push, pop で書けます．
これで計算量 $\Theta(N)$ （二分探索込みで $\Theta(N\log A)$ ）になりました．
私の解法では結構定数倍が厳しかったです．
