DreamingBoy's blog

Need help in data-structure problem.
By DreamingBoy, history, 8 years ago, In English

Hello CodeForces. Offensively that round #383 was rescheduled.

Please help me with this problem.

#CFstayalive

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Removing some room (say we want to remove the K-th room in the current configuration) can be split into two phases — first, we find at which initial index would the K-th room in the current configuration be, say that's index P, and then we say that the room at index P is removed. Obviously, answering a query of type 'L' can be done by just running the first phase of what I explained above.

Now, let's see how we can implement these phases. Suppose that up to now, we know which indices were already removed and we want to find the index of the K-th available room in the current configuration. This can be done using a binary search since this index P is the smallest P, for which P - count(P) ≥ K. Here count(i) is the number of rooms we have already removed, having indices less than or equal to i. Once we have found this index P, we just mark it as removed.

The only question that remains, is how we mark some index as removed and how we find count(i) fast enough. Well, that's pretty much what any BST does, my choice was to use treap. Sorry, I was too lazy to code one so I just copied one of my previous implementations. Here is my accepted code.

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

P_Nyagolov _index -> Thank you =D

→ Reply