@cygnus I am wondering whether this problem could be done better than O(N) with additional data structure defined.

Note that the book method was invoked incrementally to add a single additional event. But the loop for (auto & event: m) always traverse through ALL events anyway. Since this is a data structure design problem instead of given ALL N in the first place, I am wondering whether this problem is similar to problems lilke range max query, etc. (basically, we want to do efficient max of partial sum in map)