Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

MarioYC's blog

Timus 1439
By MarioYC, 13 years ago, In English
I tried to solve this problem using Binary Index Tree and Binary Search, also I used coordinate compression, keeping the positions in which I made a delete operation. Then I do Binary Search over the function

(x - (number of deleted which are less or equal than x))

the problem is that when I've deleted a number twice the function won't be motonous, hence the Binary Search fails.

Is there other way to solve it with BIT?
  • Vote: I like it
  • +2
  • Vote: I do not like it

13 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

there is no need to delete a number twice since number of the door to delete is given for the current moment, so if you store in your BIT only real numbers of deleted doors, there will never be a collision

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    but, how can I calculate real numbers for deleted doors before I start using the BIT?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      you can solve this problem online, just find the real number (like you are answering a 'L' query) before inserting a new node
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        when you say "inserting a new node" you mean I should use some Binary Search Tree?
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          oh, certainly I meant binary tree that can fast calculate number of nodes with keys in some interval like cartesian tree. but our coach said that he got accepted just supporting a sorted array of deleted rooms.

          PS: before your post I thought that BIT is the same as BST... thank you for noting about that structure! it seems to be interesting
          → Reply