DMOPC '16 Contest 2 P5 - Tormented in Tartarus

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 0.6s

Java 1.0s

Python 1.4s

Memory limit: 16M

Java 64M

Python 128M

Author:

Phoenix1369

Problem type

Tartarus is where the souls of the wicked go after death to be tormented for eternity. Among the unfortunate beings were the Danaïdes, daughters of Danaus. These unfortunate women are condemned to fill a barrel with pitchers of water until the end of time. Not only are their pitchers perforated, but the barrel they are trying to fill is as well.

It is the middle of summer and as Persephone roams above the Earth, Hades gets more and more irritable with each passing day. When taking some time off from managing the dead, Hades has decided to amuse himself by monitoring the punishment of the $N$ $N$ Danaïde sisters (labelled from $1$ $1$ to $N$ $N$ ).

All of the events which occur in the punishment will take one of the following $4$ $4$ forms:

F p The $p^{th}$ $p^{t h}$ Danaïde sister completely fills her jug with water.
D p The $p^{th}$ $p^{t h}$ Danaïde sister has her jug entirely drained of water.
R q The states of all of the pitchers are reverted to what they were immediately after the $q^{th}$ $q^{t h}$ operation was performed, undoing all of their hard work.
X The states of all $N$ $N$ pitchers are inverted (empty becomes full and vice-versa).

The pitchers of all of the Danaïdes are initially empty.

After watching $M$ $M$ operations, Hades realizes he needs to return to his work. However, for each operation, Hades would like to know the number of pitchers which were filled along with the maximum number of pitchers within the $K$ $K$ most recent operations. The latter query is to ensure the morale of the Danaïdes is never too high.

Can you write a program to help Hades?

Input Specification

The first line of input will contain three space-separated integers $N, M$ $N, M$ and $K$ $K$ , representing the number of sisters, the number of operations to be performed, and the value chosen by Hades respectively.

The next $M$ $M$ lines will each contain either just a character $c_i$ $c_{i}$ , or a character and an integer $p_i$ $p_{i}$ or $q_i$ $q_{i}$ , depending on the value of $c_i$ $c_{i}$ . The character denotes which operation is taking place, and the integers $p_i$ $p_{i}$ and $q_i$ $q_{i}$ represent the index of the sister and the index of the previous command respectively.

Constraints

$1 \le K, i \le M$ $1 \leq K, i \leq M$

$c_i \in [$ $c_{i} \in [$ D, F, R, X $]$ $]$

$1 \le p_i \le N$ $1 \leq p_{i} \leq N$

$0 \le q_i < i$ $0 \leq q_{i} < i$

Subtask 1 [20%]

$1 \le N \le 100$ $1 \leq N \leq 100$

$1 \le M \le 100$ $1 \leq M \leq 100$

Subtask 2 [80%]

$1 \le N \le 5000$ $1 \leq N \leq 5000$

$1 \le M \le 2 \cdot 10^5$ $1 \leq M \leq 2 \cdot 10^{5}$

Output Specification

After every operation, output two space separated integers on a single line:

The number of pitchers which are currently filled, and the maximum number of pitchers filled after the current operation takes place within the $K$ $K$ most recent operations (including the current one).

Note: Even though the states of the pitchers may be reverted to an earlier command, the order of the operations (and thus the last $K$ $K$ operations) are not affected.

Sample Input 1

Copy

5 9 2
F 1
F 5
F 2
D 5
F 1
D 1
R 2
R 0
F 3

Sample Output 1

Copy

Explanation 1

The $5^{th}$ $5^{t h}$ command F 1:
The $1^{st}$ $1^{s t}$ pitcher is already filled, so this command has no effect upon it.

The number of pitchers filled after the operation F 2 would be considered the $3^{rd}$ $3^{r d}$ command away, and as such its value does not contribute to the maximum of $2$ $2$ pitchers filled in the past $K = 2$ $K = 2$ operations.

The $8^{th}$ $8^{t h}$ command R 0:
The states of the pitchers are reverted to being all empty. This is because the " $0^{th}$ $0^{t h}$ " command takes place prior to any of the actual $M$ $M$ operations.

The $K = 2$ $K = 2$ states of the pitchers considered for the maximum are the $7^{th}$ $7^{t h}$ R 2, and $8^{th}$ $8^{t h}$ R 0 commands. Note the final ordering of the commands is unaffected by the reversion of the state of the pitchers.

Sample Input 2

Copy

10 7 3
F 1
X
D 1
D 9
R 2
D 3
R 4

Sample Output 2

Copy

Comments

-1

Kirito commented on Aug. 25, 2018, 2:57 p.m.

For some reason, the real constraint on $M$ $M$ is $M \leq 10^5$ $M \leq 10^{5}$ ...

12

imaxblue commented on Nov. 8, 2016, 11:48 p.m.

why tf is memory so low

1
kobortor commented on Nov. 8, 2016, 10:51 p.m. ← edit 2 →
Is it possible to revert "forwards" after reverting backwards?

Something like

Copy
F 1 D 1 R 1 R 2

This would result in something like

0

Paradox commented on Nov. 9, 2016, 1:19 a.m.

Rip XD....Hopefully not....