## Editorial for Canada Day Contest 2021 - Half Heart

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Loop through the blocks and holes after sorting them by the dimension. Let be the distance of a block to a hole in the dimension. If you fix and , you can easily find the minimum using a range minimum query. To do this range minimum query you can use a segment tree for one dimension and cdq for another. Since you don't know and yet, you can binary search for them. Now you have 4 log factors. You can remove 2 log factors by incorporating the binary search into your segment tree and cdq using something resembling a segment tree walk, always making sure the value you are binary searching matches a boundary of your segment tree or cdq function call.

**Time complexity:**

Richard: apparently turning the first dim segtree into a parallel binary search significantly improves runtime. I think it's because memory goes from to . I'm unable to get similar gains by turning the 2nd level into recursive though (that seems in line with 1D seg and div-conquer doing similarly).

The other optimization is to initialize the event queues using sorted arrays. Not doing this seems to increase my code's runtime by about 50% or so: the segtree itself is actually quite fast (due to being memory efficient I guess).

## Comments