408204: GYM103053 C Time-travelling Fan

You are Amelia Watson's diehard fan and want her to earn the most money from SuperChat among all Hololive EN members at all times. As a fan of the time-travelling detective, you naturally learned some of her time-travelling powers as well. However, it turns out that you weren't the only one!

$$$Q$$$ events will occur. Event $$$i$$$ is of the form: "A fan just donated $$$X_i$$$ dollars via SuperChat to Hololive member $$$S_i$$$ at time $$$T_i$$$." After every event, find out the minimum amount you need to spend to ensure that Amelia earns the most money among all Hololive EN members $$$\textbf {at every point in time}$$$ (she is allowed to tie with some of them). You may travel to $$$\textbf {any}$$$ point in time to donate money via SuperChat.

Notes:

- The 5 members of Hololive EN are: Amelia, Calliope, Gura, Ina, and Kiara.

- If $$$T_i = T_j$$$ then events $$$Q_i$$$ and $$$Q_j$$$ would occur simultaneously.

- We recommend using fast input-output functions as the input size is large.

- This problem may require the use of 64-bit integer data types ("long long" in C++)

The first line contains a single integer $$$Q$$$ - the number of events ($$$1 \leq Q \leq 300,000$$$)

Then, $$$Q$$$ lines follow, each consisting of a single name $$$S_i$$$, and two integers $$$X_i$$$ and $$$T_i$$$. ($$$S_i \in$$$ {"Amelia", "Calliope", "Gura", "Ina", "Kiara"}, $$$1 \leq {X_i}, {T_i} \leq 1,000,000,000$$$)

Output $$$Q$$$ integers - the minimum $$$\textbf {total}$$$ amount of money you need to spend to ensure that Amelia earns the most at every point in time after each event.

Let $$$Q_{Amelia}$$$ be the number of queries where $$$S_i = $$$"Amelia"

Subtask 1 (13 points): $$$Q \leq 3000$$$

Subtask 2 (8 points): $$$Q_{Amelia} = 0$$$

Subtask 3 (14 points): $$$Q_{Amelia} \leq 5$$$

Subtask 4 (43 points): $$$S_i =$$$ "Amelia" or $$$S_i =$$$ "Kiara"

Subtask 5 (22 points): No additional constraints

3
Kiara 50 30
Gura 10 40
Amelia 40 25

50
50
10

10
Amelia 30 25
Gura 20 20
Ina 39 60
Ina 2 1
Kiara 31 23
Amelia 100 100
Calliope 35 300
Gura 204 96
Ina 100 3
Amelia 20 1000000000

0
20
20
20
31
31
31
194
194
194

For the first sample:

Someone time-travelled to $$$T = 30$$$ to give $$$50$$$ dollars to Kiara, so you could travel back to $$$T = 23$$$ and give $$$50$$$ dollars to Amelia to make sure Amelia doesn't earn less than Kiara when Kiara's Superchat arrives.

After that, someone else time-travelled to $$$T = 40$$$ to give $$$10$$$ dollars to Gura at $$$T = 40$$$. However, you have already given $$$50$$$ dollars to Amelia previously, so you do not need to give any more to Amelia as she already earned more than Gura.

Following that, a third person travelled back in time to $$$T = 25$$$ to give $$$40$$$ dollars to Amelia. Because of this, you could travel back in time to $$$T = 23$$$, stop yourself from giving $$$50$$$ dollars to Amelia, and instead only give $$$10$$$ dollars to Amelia to minimize the amount of money you spend.