can any one tell why I am getting TLE in URBANDEV question.According to me it should pass as complexity of my code is nlogn accroding to me.
My answer link: CodeChef: Practical coding for everyone
your solution seems correct , try using fast input output like “scanf” instead of “cin”
2 Likes
Some bug in a place where you would expt it the least. Took me some time because from the first look everything seemed to be ok.
The problem is the search function, more specifically the comparators you wrote. Basic requirement of comparing ist that comp(x,y) &comp(y,x)==0 (either x may be smaller than y or viceversa, but under no circumstances both). Your definition doesn’t satisfy this (think about two points with p1.x==p2.x and p1.left==1 and p2.left==1). Using such a compare function function you will get undefined behaviour when sorting, which obviously includes running much longer than expected.
7 Likes
Got it!! Thank you very much!!
@ceilks,But according to given question such a case will never arise as no two horizontal lines can share a common point…
They can have different y-values. Say you have one hor. line at (1,3)- (3,3) and another one at (1,5)- (3,5). The left ends have both x==1 and left=1, yielding comp1((1,3),(1,5))=1 and comp1((1,5),(1,3))=1.
I got it!! Thank you very much for you help…