That’s not going to make any difference and codechef compiler won’t let you run your code with public class unless the name is Main.
Get the point of the comment dude, not the superficial stuff. The point was that the code at link was not same as what you pasted above which led to different outputs at that case.
I am sorry about that.
I do admit line-9 is different in both the codes but it’s not going to impact the output.
Also you can look at ideone code that is same as the pastebin link.
deleted…
Thank you so much for finding out the failing test case for my code.
Can you please tell me how did you got there.
I saw that the lazy propagation isnt correct implemented. After that, I just had to find a case to fail it. A large N makes it easy for me. If you try for N<100 , it can be tough or time taking to frame the case.
Because the next multiple of 2 after 10^5 is 131072 and if I had n=131072 then I need exactly 131072+131071 = 262143 integers to store whole tree without any overflow of bounds
So it’s a safe number to define size of tree when inputs are less than 131072.
Though you can use 262144 for being more safe…
Trees are always to me made about keeping n= next multiple of 2 after the real n
Not 100% sure though, but I feel you should always tend to check if any remaining update is there at the node, and then do any other check. I see you did handled it in your own way, but I cannot guarantee that its correct (it can be, but I cant say)
I think there is problem with the test cases of this problem I have seen the accepted solutions generating same output as that of mine for the test case which you mentioned.
Ok, will add it in to-see list.
In fact output of my code is correct for the test case which you have specified because other then (53-59) interval (65-67) is also active.
Looks like I made a mistake. Sorry.
Hey your problem is solved… finally… I understood your whole code
#there is some problem with shift function… line number 75 and 76 should be
lazy[id << 1] = 1-lazy[id << 1] ; lazy[(id << 1) + 1] = 1-lazy[(id << 1) + 1] ;
#instead of
lazy[id << 1] = lazy[id] ; lazy[(id << 1) + 1] = lazy[id] ;
Its obvious here we have to flip the lazy segment each time it needs update… no need to make it as parent…
#let’s say I have 2,3 child nodes and 1 as parent
and 2 is marked and 3 as not
#then if I update node 1 then I have to make
3 as marked and 2 as not… obviously…
#just flip it…
2 Likes
one more overflow problem is you don’t need shift when it’s a leaf…
but It won’t give wrong answer as your array declaration size is too large…
#but surely…
`
if (lazy[id] > 0)
#should be
if (lazy[id] > 0 && start!=end)
`