Four problems about records and repeats: words printed with their repeats in order, the best score of every team, the longest run of songs with no song played twice, and a pattern counted with the help of positions.
- Words in dictionary order, repeats included: a
multiset<string>does it all. - For every team, keep its best score and how many times it was reached in two
maps, and print
best.size()first. Team numbers can be negative — the map still sorts them correctly. Up to 2·10⁵ results: fast IO. - For the songs, remember where each song was last played. The run only has to move its start when the earlier copy is inside the run.
- It's Mooin' Time II is the hardest. A moo is
a b bwitha ≠ b. For a valuebthat appears at least twice, use its last two copies: then anya ≠ bthat appears before the second-to-last copy makes a moo. So, for every suchb, count the different values before that position — the size of a set as you go, saved in a vector — minus one ifbitself is among them. The answer needslong long.