dv.jakhar_'s blog

Assignment to segment [ Segment tree Lazy ] [ Solved ]
By dv.jakhar_, 4 years ago, In English

Can someone please help me with this problem. Here is my solution. It's giving me wrong answer on test 2. I am applying simple lazy prapogation logic. Can someone help me, It will hardly take 5 minutes of your time.

My logic: Firstly I fill the whole segment tree with -1's. Now, query function is simply finding an element present on a particular index and when we have some update pending in the path from root to this node I will simply assign this value to it's children and current node will have value -1 after this. My english is poor, sorry.

Thanks very much.

Upd: Accepted code

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

You should push values in update function too. For example, suppose you have this test:

8 3
1 0 8 123
1 0 0 456
2 0

Then you assign value $$$123$$$ to tree[0] and finish update. Then you get next query, go to leaf node without pushing $$$123$$$, and just put $$$456$$$ in the leaf. But then, when you get a query for this leaf, you push $$$123$$$ down and overwrite $$$456$$$, getting wrong answer

→ Reply