I have used mo’s algorithm to solve this question… But still I’m getting TLE!!!
And I can’t understand why I’m getting TLE for different test case numbers by doing minor changes. (The overall time complexity should remain same even after doing these changes!)
This code gives TLE on test case 41,
This one gives TLE in test case 43 (Removed sorting step from previous code and instead stored results in a different array)
Thanks the link really helped! But can you tell me @meooow why such small modifications like converting ll to int and using inline functions have so much effect on running time!
Yup, thanks to @meooow for cool info. Btw, I know the reason for inline function. By using inline function, the compiler inserts the body of the function wherever you call the function and thus no stack push/pop operations for function calls and stuff. This saves time.
Well the trick used in sorting is quite fascinating though 
Yes @dishant_18 is right about inline functions. Only one correction, the inline keyword is only a suggestion to the compiler, and the compiler may decide not to replace the calls with the function body.