Why Segment Tree For CCIRCLES failed ?

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!

This solution is quite unoptimized as my solution is O(n^2 + max(k) + q) and query was expected to be O(1)…
But your solution is quite hard to pass if you don’t optimize it much…
I can see some solutions of lazy propagation which passed in about 0.9 secs…

Don’t use double much… (PS my solution don’t contain double at all !!)
And it runs in 0.06 seconds…

//