I was solving this question on codeforces, and was getting TLE for large test cases. I read a blog about different implementation for compare function on coderfoces and changed my compare function to the third option.

After reading a comment saying that bigger sq can decrease runtime, so decided to give it a try. And it worked, I changed my sq size to 1000 and code was accepted.

What I want to ask is

- How size of sq ( = sqrt(n) ) changes runtime?
- Should I choose a considerable size myself?
- How can I optimize my code as it is just passing by bare minimum of time limit?

can you explain point 2, please?

In the input you have n integers and all of them need to be divided by s (a is square root of n, you calculate it once and it remains constant for the rest of the program) so you can have another another array ndiv[n] which stores every element of the input divided by s. If numbers are too big you can just remember which element of an array you use (in comparator change a for arr[a]). Because of this you don’t have to use operation divide nlogn times but just n.

3 — You should be able to save a lot of time just by using

`'\n'`

instead of`endl`

to output the result of your queries, as there's no need to flush the output. This should save you enough time to be decently far from the TL :)thank you, time reduced to about 80% of the time limit.