I have also tried by copying input class from one AC solution but I am still getting the WA.
I fear that you gave wrong solution link for pastebin then. The solution at that link gave
0
1
3
as output
I dont think this is the code given at link. Just check line no. 9 in both. Its public class FlippingCoins here, and only FlippingCoins there
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.
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
Can you look into this.
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.