adamantium's blog

Facing problem in spoj RACETIME — Race Against Time
By adamantium, history, 8 years ago, In English

I tried this problem with segment tree first and got TLE. Then I used square-root but again got TLE. To solve the problem with square-root i used tree which size is sqrt(n) * sqrt(n), where n is the size of the array. In every block of the tree I kept sqrt(n) elements of the array sorted in ascending order. When update occur I push the element in a block where it's index remain and again sort this block. And when i got query operation for every block which is in the range I found how many elements are less than the given value. This can be done with binary search for every block. Please tell me where i should optimize my code. Here you can have a look at my code .

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Cant u just use some BIT instead of resorting block everytime?(i mean, to update with O(log(n)) instead of O(sqrt(n)*log(n)))

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Then we should compress the value of the array. Isn't it???

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am having problem with it too. First, i used BIT which made complexity of per update log(n) and per query sqrt(n)*log(n) + sqrt(n). But i got TLE. I don't know why! Then, i used 2D BIT and update became log(n)*log(n) and query log(n)*log(n) + sqrt(n). But still getting TLE. Please help me. Here is my Code . Thanks in advance.

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

UPD: Problem Solved :)

→ Reply