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

Автор arham_doshi, история, 4 года назад, По-английски

need help in this question. question ask you to implement two types of lazy trees one for update and one for sum. I did all I could but i am unable to find the bug. please help me .

my code
test case
required ans
my answer


it would also be help full if you know some blog or toutorial to solve similar problem. thanks in advance guys for helping.

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

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

Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).

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

So

  1. Your code contains a lot of hindi comments which makes it irritating to read

  2. You use different spacing techniques (3 spaces in main, 2 spaces in segtree).

  3. You don't add any spaces after ,,|,& et.

  4. You have weird blank lines.

  5. You have like a million debugging lines.

  6. You are using weird loop defines.

...

You could have removed useless stuff and run a formatting tool on your code to make it somewhat readable. Why should total strangers help you if you can't even do that? What are you expecting by throwing this pile of ugly code at people? You even have a testcase which your code doesn't work on I think you should debug by yourself. And why is this blog at +4? I'd argue such stuff should be forbidden on cf at best.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    really sorry about it . It is nice feedback i will see it in furture. thing about debugging myself is i tried it for 2 hrs a lot of debugging but i am not getting a tiny bug. when i print the query (in which i am getting wrong ans ) after after every operation it is giving write ans. a soon as comment it again the ans is worng . it is frustrating man and the blog is my last resort.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

      i tried it for 2 hrs

      ~~ Rookie numbers make that 5 times more~~

      So I skimmed through your code:

      Your probably should change 2*n to 4*n

      You store everything as int but sum can overflow i guess

      Sometimes add update can be stacked on top of set update and you are always stacking it into add updates


      3 3 0 0 0 2 1 2 1 1 1 2 1 3 1 1

      Your code prints one because in the second query you add 1 to sum lazy, which is in fact overwritten by set lazy(from query 1). Instead you should have added 1 to set lazy so the operation becomes "set to two".

      Keeping two lazy tags can mess with order instead I suggest storing one tag, and it's type.

      Here's a short implementation of this idea

      I am really bored
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        thank you so much kostia . i it worked . i learned alot from you code. it was superb.

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

It's quite hard to understand your code...

So if you want then can look at my code.

My approach is quite lengthy , so unable to explain it here.

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

Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).

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

In the following solution if I swap the first and second line in update() that is


if(l>r) return; push(v, tl, tr); // if you put this after (l>r) return statement, you'll get WA

Can someone help me with why this order matters? Because we are anyways returning if l>r?

Solution code

Thanking you in advance.

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

    Don't push without later merging your two children.

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

      Errichto Thank you very much __/\_ . If I interchange the lines, the children node is marked lazy(but t[children] is not updated) and hence it updates the parent with old value.