### rpkv's blog

By rpkv, history, 2 months ago, ,

https://codeforces.com/contest/1278/submission/75598239 Prob D DIV2 Educational Round 78.. https://codeforces.com/contest/1278/problem/D Can someone please help me figure out why my code gives TLE on TEST 49 ? It would be a huge help ! Thanks in advance!

• -11

 » 2 months ago, # |   0 Hello! From what I could tell by looking at your code, you seem to be iterating through every possible pair of segments, checking for intersections, and then checking to see if the resulting graph is a tree. The problem is that iterating through every pair of intersections takes $O(n^2)$ time, which is way too much for $n < 5 \cdot 10^5.$ Could you find a more efficient way to find all pairs of intersections?
•  » » 2 months ago, # ^ |   0 Hey ! Thank you for your reply !. I guess I am unable to understand how in the editorial we are finding all pairs of intersections in less than O(n^2) time.
•  » » » 2 months ago, # ^ |   0 I think I finally got it !. We need to sort on the basis of starting points AND ending points in order to avoid unnecessary checks where one segment is contained inside the other. We break the process when we reach n intersections