Thanx a lot
can you please tell how the binary search is working . i can’t able to understand it.
please tell the idea of using the binary search here
Because the three arrays will have a length of 1 820 598 elements, which combined with the 10^5 test cases will result in an TLE if you iterate over them for each test case. Another approach could be to first read in the indexes that are needed; then make the arrays and calculate the corresponding values as you come across them, but that is a little harder to implement.
1 Like
In C/C++ array name is starting location of an array. So here prefixSum refers to starting location of prefixSum array. And the whole expression is used to calculate the index at which element ‘n’ is present in prefixSum array.
1 Like
Oh yeah Thanks , now I remember it
The question states that L and R can be upto 10^10. But we are only declaring golomb array upto 2*10^6.
ll g[SIZE], prefixSum[SIZE], prefixSum2[SIZE];
How are inputs of L and R which are above 2*10^6 handled?
Thanks in advance
1 Like
Prefix and prefix contains values and not the golomb sequence … the value corresponding to max input(10^10) is 2 10^6 , so they are okay with sizes 2 10^6 however I am unsure as to how it works for g[], If someone who understands the logic explains it, then it would be awesome 
1 Like