Why Segment Tree For CCIRCLES failed ?


#1

Here is the problem link
https://www.codechef.com/OCT18B/problems/CCIRCLES
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!


#2

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…


#3

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