When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

arham_doshi's blog

By arham_doshi, history, 4 years ago, In English

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.

  • Vote: I like it
  • -25
  • Vote: I do not like it

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

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

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

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 3   Vote: I like it +7 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Don't push without later merging your two children.

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

      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.