TLE in frogv.

general
,
1

Help getting TLE in frogv I sorted cordinate using quick sort and then go from min coordinate to max coordinate and note down every starting point after breaking point say if coordinates are 0 8 5 3 12 and distance is 3 than I stored 0 12 in new array than I take input from user and get coordinate of there position and look for whether they belong to same interval or not if yes than answer is yes else no. Link to solution Please tell me what wrong in my code

2

Your solution is a linear time algorithm for every query ,
So the worst case complexity of your algorithm is O(NP) . According to the constraints N <= 10^5 and P <= 10^5 , So NP = 10^10(which is huge) in the worst case so It should get TLE:
It is clear that your program cannot run in the designated time of 1 sec as given in the problem .

If you want to get AC in the program using this logic then you should check out this data structure:
Segment tree


http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static

2 Likes
3

Thanks for answering

1 Like