help in optimizing code...

question : https://www.codechef.com/problems/BGQRS

my solution : (N * sqrt(N)) : https://www.codechef.com/viewsolution/15093155

my solution was failing only the last case…i know that manyone have solved this using sqrt decomposition, so, it’s possible but i cannot able to optimize it further can anyone please help me !

Square root decomposition wasnt the intended solution and author wanted it to fail

However, one of the square root decomposition solution of @pkacpraz did pass. You can see his explantion here -http://chasethered.com/2016/10/unofficial-editorial-big-queries-from-codechef-october-long-2016/?ref=codechef

//