D - Election Quick Report Editorial by spheniscine


Imagine a set of tuples \((-C_i, i)\) for each candidate, where \(C_i\) is the current number of votes for candidate \(i\). Then the winner of the election is the candidate with the lowest tuple.

You need a data structure that models a set with remove, add, and query minimum operations; most programming languages come with an “ordered set” data structure in its library that implements those operations in \(O(\log N)\) each. In C++ it’s std::set, in Java/Kotlin it’s TreeSet, and in Rust it’s BTreeSet. Thus the problem is solved in \(O((N + M) \log N)\). Then whenever a vote is cast, you can remove the old tuple for the candidate, replace it with a new tuple, and then query the winner of the election using these operations.

You can also solve this problem with other data structures, like a segment tree or a binary heap, though you’d likely have to manually code those. (or use the AtCoder library)

posted:
last update: