\(O(N \log N)\) で解けます。

公式解説の貪欲法は、入次数が 0 の頂点のうち最大の番号 \(i\) を選び、 \(i\) から出ている辺を削除する、と言い換えられ、これで \(O(N^2)\) になります。

分割統治法を用いて辺の数を減らすことを考えます。

solve(l,r)では、\(m=(l+r)/2\) としたときに、\(l \le L_x < m \le L_y < r\) となる \((x,y)\) についてのみ考慮することにします。再帰的に solve(l,m) , solve(m,r) を呼ぶことで全ての\((x,y)\) を網羅できます。

solve(l,r)では、\(l \le L_x < r\) を満たす全ての \(x\) について、 \(R_x\) に対応する補助的な頂点を作ることで、頂点、辺の数をともに \(O(N \log N)\) にできます。

補助的な頂点のうち入次数が 0 のものがあれば即座にそれを選べばよく、ない場合の最大の番号は優先度付きキューで取得できる (この操作は\(O(N)\) 回) ため、全体で \(O(N \log N)\) で解けました。

実装例

(ARCネタバレあり) を参考にしています。