E - Wrapping Chocolate Editorial by sugarrr


まず、チョコレートと箱をまとめて、縦の長さの降順にソートしておきます。ただし、縦の長さが同じチョコレートと箱があるときは、箱を前に並べておきます。

空の数列 \(S=()\) を用意し、要素を前から次のように見ていきます。

  • 見ている要素が箱 \((C_i,D_i)\) のとき
    \(S\)\(D_i\) を追加します。

  • 見ている要素がチョコレート \((A_i,B_i)\) のとき
    \(S\) の要素で \(B_i\) 以上のもののうち最小のものを削除します。もし削除するものが存在しなければ、答えは No です。

最後の要素まで見終えることができたら、答えは Yes です。

上記を愚直に実装したときの計算量は \(O(NM)\) と遅いですが、\(S\) として C++ の std::multiset を用いたり、座標圧縮してセグメントツリーを用いたりすれば \(O((N+M)\log (N+M))\) になり十分高速です。

posted:
last update: