jha_gaurav98's blog

Problem in a segment tree question PSTRG
By jha_gaurav98, history, 7 years ago, In English

I was solving the question PSHTRG. Basically it is a segment tree problem. I stored 45 greatest elements of each range as the node in segment tree and then for each query I used these elements to find the answer. But my code is giving TLE. I think there is nothing wrong with the logic but I am not able to optimize the code. Please can someone help. Thanks in advance.

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

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Your update function works in O(N).You must add this "if(l > x || r < x) return;" to make it O(logN). And then your code should be accepted.

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

    Thanks a lot friend. I just can't believe I missed that and wasted a lot of time.

    → Reply