Let us consider how to simulate the process fast.

It seems to be sufficient if we can manage who are in the line and when those who are not in the line are coming back.

Prepare a priority queue \(Q\) to take two types of events, “noodles are flown down” and “a person has come back”, in order of occurrence, and an ordered set to manage whose is in the line, and process the events as follows.

• Take an event from \(Q\).
  • If the event is “a person has come back”, insert that person to \(S\).
  • If the event is “noodles are flown down”, take the person with the minimum index from \(S\), update the amount of noodles that the person has got, and insert an event that “that person has come back” into \(Q\).

An event is taken out from \(Q\) at most \(2M\) times in total (\(M\) are “noodles are flown down”, and the other \(M\) are corresponding “a person has come back”), and an event can be processed in an \(O(\log N+\log M)\) time, so the simulation can be performed in a total of \(O(N+M\log N+M\log M)\) time.

Writer’s solution (C++)