Help — OII 2021 Practice "Allenamento su ChinaForces"

Revision en1, by Bungmint, 2022-04-12 00:04:59

Problem Link: Link

Hi everyone.

I was just going through problems on USACO gold section trying to solve problems with difficulty tags of "Hard" and found myself stuck in the problem mentioned in the title. I was able to come up with a $$$O(nlogn)$$$ solution involving small-to-large merging technique, but I could not come up with an $$$O(n)$$$ solution that is required for the last two points. I looked up for tutorials online and came across a comment on codeforces: Thread under the OII 2021 announcement, but I still do not understand how to store the candidate minimums in an efficient way. Any help would be much appreciated :)

Tags tagsareoverrated


  Rev. Lang. By When Δ Comment
en1 English Bungmint 2022-04-12 00:04:59 811 Initial revision (published)