Editorial for King of the Hill
Remember to use this editorial 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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Problem Statement Simplified
Essentially at any given moment you have a set of numbers. Queries will either make you remove a maximum number (there may be multiples), output the maximum number, or add another number to the set.
Solution
In order to solve this problem, you must use a sorted structure.
Due to time constraints, insertions should take approximately , deletions should take at least
, and getting the maximum should be near-instant, around
.
A priority queue, balanced binary search tree, or multiset can all be used to achieve these requirements efficiently.
Time Complexity:
Comments