In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Byteasar is a programmer who works on a revolutionary text editor.
In the editor there are two types of operations: one type allows to edit text in the editor,
and the other type allows to undo previously performed operations.
One of the innovative features of this editor is a multilevel undo operation.
It works as follows.
We say that a text editing operation is an operation of level 0.
An undo operation of level (for
) undoes the last operation of level at most
which is not undone.
For instance, an undo operation of level 1 can undo only editing operations,
and an undo operation of level 2 can undo editing operations as well as undo operations of level 1
(but no undo operations of greater levels).
More formally, each of the already performed operations can be in two states: active or undone.
Let be one of the operations.
Just after performing the operation
, it is in the state active.
If
is an undo operation of level
, we find the most recent operation in state active
of level at most
(denote it by
) and change the state of the operation
to undone.
If
is also an undo operation, we must change to active the state of the operation which
had undone (say
).
We continue in the same manner: whenever the state of an undo operation
which had previously undone
some operation
changes, we must also change the state of the operation
(which, of course, may result in changing states of further operations).
The whole chain of state modifications finishes when an editing operation is reached.
For simplicity, the current contents of text in the editor will be specified by a single
integer , called the editor state (equal to 0 at the beginning).
Each editing operation specifies the editor state that it produces.
The editor state depends on the last editing operation in the state active.
Help Byteasar and write a program which keeps track of the editor state.
Let us see this in action: the following table shows some operations performed by Byteasar
and the editor state after performing each of them. The symbol denotes
an editing operation which changes the editor state to
, whereas the symbol
denotes
an undo operation of level
.
Operation | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
Editor state | 0 | 1 | 2 | 5 | 2 | 1 | 2 | 4 | 2 | 1 | 0 | 1 |
First, Byteasar performed three editing operations.
The editor state changed from 0 to 1, then to 2, and finally to 5.
Next, he performed two undo operations of level 1, which undid the operations and
(changing their state to undone).
Thus the editor state was restored to 1.
The following undo operation of level 3 undid the last operation
(changing its state to undone),
consequently restoring the operation
(changing its state back to active).
As a result the editor state changed once again to 2.
Operation
undid the operation
, operation
once again undid the restored operation
, the last
operation
undid the operation
, and the final operation is
.
The first line of the input contains a positive integer , specifying the number
of operations performed by Byteasar. The next
lines contain descriptions of operations, one per line,
each being an integer
(
,
). If
, then it specifies an
editing operation which modifies the editor state to
. If
, then it specifies an undo
operation of level
.
You can assume that for every undo operation there will be some operation in the state active of smaller level to undo.
Your program should output lines.
The
-th line should contain one integer specifying
the editor state after performing the first
operations from the input.
For the input data:
11 1 2 5 -1 -1 -3 4 -2 -1 -1 1
the correct result is:
1 2 5 2 1 2 4 2 1 0 1
Subtask | Conditions | Points |
1 | ![]() | 20 |
2 | ![]() ![]() ![]() | 15 |
3 | ![]() ![]() ![]() ![]() | 28 |
4 | ![]() | 37 |