Official
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: