| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 7 | 3 | 2 | 40.000% |
Wow, your to-do list is empty...but not for long! Over the next few seconds, you’ll have to handle $Q$ updates to your to-do list.
For the first type of update, you will have to add a new homework assignment to your to-do list. This assignment will be released at the beginning of second $s,ドル and will take $t$ seconds to complete (1ドル ≤ s, t ≤ 10^6$). For the second type of update, you will have to remove the $i$-th homework assignment that was added to your to-do list.
After each update, you wonder: what’s the earliest time you can finish all of the homework assignments in your to-do list? You can only work on one assignment at a time, and you must finish a homework assignment once you start it without switching to another assignment.
The first line of input contains an integer $Q$ (1ドル ≤ Q ≤ 10^6$).
The next $Q$ lines each contain a line starting with a character A or D. A line starting with A represents the first type of update and ends with two space-separated encrypted∗ integers $s'$ and $t'$. A line starting with D represents the second type of update and ends with an encrypted integer $i'$. It is guaranteed that there have been at least $i$ assignments added and that the $i$-th assignment to be added has not been removed yet.
It is guaranteed that there is at least one homework assignment on your to-do list after every update.
∗Note that the input for this problem is encrypted. To decrypt and obtain the actual values of $s,ドル $t,ドル and $i,ドル you may use the following formulas:
Here, $ans$ represents the answer after the previous update and is initially 0ドル$ before any updates. It may also be useful to note that mod corresponds to the % operator in most programming languages, indicating the remainder after division. For example, 5ドル \bmod 3 = 2$ and 17ドル \bmod 4 = 1$.
Output $Q$ lines, where the $i$-th line contains the earliest time (in seconds) you can finish all of the homework assignments in your to-do list after the $i$-th update.
6 A 3 3 A 2 0 A 999996 999995 D 999991 A 1000000 999994 D 999992
5 11 13 11 13 9
Sample Input 1 (Unencrypted)
6 A 3 3 A 7 5 A 4 3 D 1 A 8 2 D 2
The unencrypted sample input is provided for ease of reference.
After the first update, we can start the first assignment at the beginning of second 3ドル$ and finish at the end of second 5ドル$ (interval $[3, 5]$).
After the second update, we can do the first assignment over the interval $[3, 5]$ and the second assignment over the interval $[7, 11]$.
After the third update, we can do the first assignment over the interval $[3, 5],ドル the third assignment over the interval $[6, 8],ドル and then the second assignment over the interval $[9, 13]$.
After the fourth update, we can do the third assignment over the interval $[4, 6]$ and the second assignment over the interval $[7, 11]$.
After the fifth update, we can do the third assignment over the interval $[4, 6],ドル the second assignment over the interval $[7, 11],ドル and the fourth assignment over the interval $[12, 13]$.
After the sixth update, we can do the third assignment over the interval $[4, 6]$ and the fourth assignment over the interval $[8, 9]$.
2 A 1000000 1000000 A 4 4
1999999 2999999
Sample Input 2 (Unencrypted)
2 A 1000000 1000000 A 1000000 1000000