S5. To-Do List
레이팅 미적용의견: 0
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 \le s, t \le 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.
\((1 \le s, t \le 10^6)\)
The first line of input contains an integer \(Q\).
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:
$$
\begin{align*}
s & = (s' + \text{ans}) \bmod (10^6+3)\\
t & = (t' + \text{ans}) \bmod (10^6+3)\\
i & = (i' + \text{ans}) \bmod (10^6+3)
\end{align*}
$$
Here, \(\text{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.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 13점 | \(1 \le Q \le 3 \, 000\) — None |
2 | 40점 | \(1 \le Q \le 10^6\) — Only updates of the first type |
3 | 47점 | \(1 \le Q \le 10^6\) — None |
6
A 3 3
A 7 5
A 4 3
D 1
A 8 2
D 25
11
13
11
13
9The 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 1000000 10000001999999
2999999평가 및 의견
S5. To-Do List
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
S5. To-Do List