Editorial for DMOPC '21 Contest 7 P2 - Knitting Scarves
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Hint
Doubly Linked List.Full Solution
We will perform these queries on a Doubly Linked List to achieve a constant time.Each node in this Linked List will represent a node with a certain value. Each node will have a pointer to the next node and a pointer to the previous node. Thus, initially the node that holds value
When performing a query, it helps to see for every relevant part of the Linked List how will their pointers change. For a particular query
1.
2.
3.
The query makes
1.
2.
3.
When setting
Be careful when implementing. In particular, first take out the array that starts with value
Comments