Here is the problem link
My approach:
1)Pairwise calculate relative positions of all circles given .
2)Calculate min and Max dist between them.
3) Update the [min,max] range by incrementing it by 1.
4)For every query calculate answer in log(n) time.
Here’s my solution link
https://www.codechef.com/viewsolution/21040808
Now,Let’s analyze each step.
1)Since n=1000 pairs are of order n^2 that is 10^6.
2,3)Since max distance is also of order of n^2 Updating range with every pair costs O(n^2log(n^2)) with lazy updates. So it takes 10^6 20 steps ie 2*10^7.
4)Lastly, every query q is answered in (O(log(n^2)) time making it 20 * 10^5 steps.
Total Time = n^2 + n^22log(n) + m * 2 log(n).
How did it fail the time limit ? Thanks in Advance!