E - Wrapping Chocolate Editorial by en_translator
First, make a list containing all the chocolates and all the boxes, and sort it in the decreasing order of their widths. If there is a chocolate and a box with the same width, order the box first.
Prepare an empty integer sequence \(S=()\). Inspect each element as follows.
If the inspected element is a box \((C_i,D_i)\)
Add \(D_i\) to \(S\).If the inspected element is a chocolate \((A_i,B_i)\)
Remove the smallest element of \(S\) greater than or equal to \(B_i\). If there is no element to remove, the answer isNo
.
If all the elements were successfully inspected, then the answer is Yes
.
The naive implementation of the solution above is as slow as \(O(NM)\), but we can use std::multiset
for \(S\) or use a segment tree after compressing coordinates so that it can be solved in a total of \(O((N+M)\log (N+M))\) time, which is fast enough.
posted:
last update: