まず、条件について整理しましょう。

• \(A_i < B_i\)
• \(A_1, B_1, A_2, B_2 \cdots, A_N, B_N\) が全て異なる

の下で考えます。

\(1\) 階で乗った人が降りる階を \(x\) 階とすると、\(2, 3, \cdots, x-1\) 階で乗った人はそれぞれ \(x + 1, x + 2, \cdots, 2x-2\) 階で降りることがわかります。

この議論を繰り返すと、\(2N\) 階を \((A, B)\) が \((x, x+k), (x+1, x+k+1), \cdots, (x+k-1, x+2k-1)\) の人が乗り降りするような区間に分割できることと同値であることがわかります。

では、区間の分割を固定したときに、そのような分割となるように \(A, B\) を埋める方法があるか判定することを考えてみます。

各階にその階で乗る/降りる人が決まっていれば (左向き/右向き, 人のid) を対応させた配列を保存しておきます。

区間ごとに、 - \(A, B\) ともに決定している人で片側だけある区間に含まれているような場合がない / 両方含まれるならばペアの位置がずれていない - ペアの両側の人がそれぞれ決まっている場合、同一人物である - ペアの左側のtypeが\(左向き\)でない - ペアの右側のtypeが\(右向き\)でない

が必要で、また全ての区間についてこの条件が満たされていれば、適切に \(-1\) を埋めることで正しい記録が \(1\) つ求まります。

よって dp[\(i\)] := \(i\) 階でちょうど区間が終わり、\(i\) 階までで矛盾していないならば true, していれば false のような配列を持ち、新たに 区間\([i+1, r]\)が矛盾していなければdp[\(r\)]をtrueにするようなDPで判定することができます。

計算量は \(\mathrm{O}(N^3)\) です。

実装例(2020/10/08追記)

誤実装例(後ほど誤りがあることが発覚しました)