Contest Duration: - (local time) (100 minutes) Back to Home

D - Cylinder Editorial by en_translator

Store the state inside the cylinder in the Run Length encoding.

In other words, store the state after the following queries

1 2 3
1 3 4
1 10 10

in the format of “$$3$$ twos, $$4$$ threes, and $$10$$ tens.” Since each query increments the length of this list by at most $$1$$, so the length does never exceed $$Q$$ overall.

By storing the information of this format, each insertion query can be processed in an $$O(1)$$ time, and each take-out query in an $$O(1+(\text{the number of elements removed from the deque}))$$. Therefore, the problem has been solved in a total of $$O(Q)$$ time.

Note that this problem can in fact be solved without the Run Length encoding. For example, the state of the cylinder after the queries

1 10 3
1 10 10

is encoded as “$$13$$ tens,” but we can just keep it as “$$10$$ tens, and $$3$$ tens” without changing the complexity from $$O(Q)$$.

posted:
last update: