Here’s the link to my solution : [link][1]
The editorial says that an n.logn solution should pass… Why is it giving a TLE, then? 
[1]: http://www.codechef.com/viewsolution/5648198
Merge sort although working in O(nlogn) time isn't cache friendly and has high constants!
Try using the inbuilt sort function. If you have some special comparisions to make, you can overload the '<' operator too!
You can learn that here : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2
Reading your code, I think this is equivalent to what you wanna do:
struct frog{
int xcord;
int index;
};
bool operator<(frog a,frog b){
return(a.xcord<b.xcord);
}
this will sort the frogs if you make an array of structure frog and use the inbuilt sort! :)
Also: http://www.codechef.com/viewsolution/4185285
This is the solution using the above method in case you get stuck!
Happy coding! :)
1 Like
Thanks… That link is really good! I’ll read it and try solving it again 
I used merge sort for the same problem.
http://www.codechef.com/viewsolution/4249336
AC time = 0.22 secs
Will it also get AC without the fast input? o.O
of course!
http://www.codechef.com/viewsolution/5678705 - replaced fastread function body with scanf
0.3 secs o__o
I always used mergesort when I used C and not once did I face a tle when quicksort had been accepted. So even though the constants are high, they are not high enough to cause TLE wrt quicksort if the implementation is good enough unless the time bounds are very tight and that wouldn’t make a good problem either.
Will you check my solution, then? What am I doing wrong there?
@ajinkya1p3 the only thing you are doing wrong is taking inout in the wrong manner . The input will follow like this - N,K and then P while you are taking N,P and K
1 Like
Ohhh no…! Thanks bhaiyya!
I did the same mistake during the contest and wasted 2 complete days doing research on speeding sorting by using three way and four way merge sort. The third day I realized the n and k order was reversed 
1 Like