Блог пользователя dv.jakhar_

Автор dv.jakhar_, 4 года назад, По-английски

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

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

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

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