Need debugging BGQRS code

general
, ,
1

I have been trying this problem for two days now, and have not been able to understand the problem with my code. It looks perfect to me and even after about 30 submissions I have not been able to get it correct. Someone please help me find any bug.
Problem link : BGQRS
My code link : Ideone Code

Thanks :slight_smile:

2

I believe the error is in handling numbers larger than 10^18 . I ran your code on a test case, and it failed.

Input
1
5 3
1000000000 1 1 1 1
1 1 5 1000000000
1 1 1 1000000000
3 1 5
Your Output
36
Expected Output
63

I verified the output by cross checking with various C++ implementations, and they all yield correct output. I am sure that this case is the one agonizing you here.

1 Like
3

Thanks vijju123 , the error wasn’t in handling large numbers, but silly mistake in update()
I was adding number of twos in left child and number of fives in right child while I had to update both in both the childs. :stuck_out_tongue:
Brain’s dead :smiley:

4

It reminds me when i traumatized 2 days over SPOJ’s ‘Frequent’. I was getting WA in final cases. And after 2 days, do you know what i got? Instead of declaring tree as "tree[4*n+10]" i allotted it less memory and declared it "tree[2*n+1]" . Correcting it got me an AC.

5

That AC after days of frustration, is what we long for. :slight_smile:

1 Like