Have you tried the example cases?
I think you should not do the l+1 and r+1 in lower_bound and you might need to look at cases where the range starts at one.
I too thought of that
and submitted another solution in which i have taken l and r instead of l+1 and r+1, rest same
So i think that is not the issue
https://www.codechef.com/viewsolution/36011555
Then I am not sure.
If you want to try random test cases, here is my submission
That big ugly block at the top is a self-made class Mod that takes care of all modular arithmetic. It makes it so that I can use modular arithmetic as if they are normal integers.
1 Like
OK 
on test case
1
1 10000000000
my answer is 258479624 which is wrong as your answer is 123983151
God knows why
Found the issue.
From another discussion thread, place the following at the start of your code
#pragma GCC optimize "trapv"
and compile. This will instruct to fail whenever an integer overflow occurs.
Then running in GDB we find that it fails at line 31. This is because i is an integer and therefore too small to fit i*i, change to an long long an it will work.
3 Likes
oh fuck me fuck me fuck me fuck me
1 Like
Nice editorial. And 6 star! Congrats.
3 Likes
Now it gives AC
changing int to ll
Thanks for pointing it out 
1 Like
No problem.
The 6 star feels weird. I have gotten so used to 5 star that the orange feels out of place. Might take some getting used to it.
2 Likes
Hey, now you have learned about the trapv pragma. It was also the first time that I tried that pragma and I am amazed how quickly it spotted the error. And now you know that you could have solved this problem with what you already knew.
3 Likes
Yeah thanks
i am never using int again in my whole life
I made the same mistake. Not gonna use ints anymore XD
1 Like
Can you please explain 3rd case in Golomb Sequence. Why did you do i*i and what GB[i+1]!=GB[i] means?
1 Like
I have rephrased the definition of the third array a bit. It was indeed stated confusingly/incorrectly.
For naming let’s call that array preAns. Then
\texttt{preAns[i]}=\sum_{j \text{ for which } \texttt{golomb[j]}\leq i} \texttt{golomb[j]}^2=\sum_{j=1}^i\texttt{golomb[j]}\cdot j^2
This way if we want the ans for a range 1\ldots R, i.e. we want to calculate \sum_{i=1}^R\texttt{golomb[i]}^2, and we now that \texttt{golomb[R]}=v we can split this sum up:
\sum_{i=1}^{\texttt{GC[v-1]}}\texttt{golomb[i]}^2+\sum_{i=\texttt{GC[v-1]}+1}^R\texttt{golomb[i]}^2 = \texttt{PreAns[v-1]}+(R-\texttt{GC[v-1]})v^2
2 Likes
Can you please describe why you took array length to be 60 in the first problem? Thanks
That was left over when I tried saving it in the total length. I believe it could be 30/31.
The length could be 30/31 because Ai has maximum value of 2^30 right?
I believe so, try it.
Thanks for the beautiful explanations.