svg_af's blog

Memory limit with Persistent Segment Tree
By svg_af, history, 8 years ago, In English

Hello There

I'm trying to solve this Problem using a persistent segment tree

I keep getting TLE for reasons i can't find

If anyone would so kindly explain the reason behind the memory leak it would be really appreciated

Here is my code

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

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

query function shouldn't create new nodes. It's horrible.

You have O(N·log2(N)) space complexity with this code.

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

    You are right !!!

    fixed it and got my AC thank you so much :D

    btw i have to say .. nice pic :D

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

You got ML, not TL. You programs eats too much memory. That's exactly because of persistent segment tree, as you save all previous steps and it needs a lot of memory.

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

I am also facing the same issue. Can someone check my code and tell why it is giving MLE.

79459003

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

This was very nice question ... I did it now .. Great question

Thanks a lot bro

→ Reply