Блог пользователя svg_af

Memory limit with Persistent Segment Tree
Автор svg_af, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

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

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You are right !!!

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

    btw i have to say .. nice pic :D

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

79459003

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Thanks a lot bro

→ Ответить