U can see in the video that the complexity is O(Nlog N)+R where R is the number of intersections.
Suppose you have x horizontal and y vertical lines,maximum number of intersections will be x * y(This is similar to selecting 1 horizontal line and 1 vertical line).U can find maximum number of intersection using A.M>=G.M rule which will be (N * N)/4.
Hence just by using Sweep Line algorithm the complexity becomes O(Nlog N)+O(N * N) which is same as O(N * N) which results in TLE.U can refer to this code which got TLEs in 2nd subtask
Now what shall we do??
U can easily observe that total number of intersection points is basically the sum of intersection points of each individual line divides by 2.We will use this fact to find out the answer.Basically we have to find the answer for each individual line first and then use it to find the number of intersections.
Instead of iterating through all the possible values in that range we can use BIT or segment tree to find the answer in O(log N)
After that we have to subtract all those points which are end points of both vertical and horizontal lines which can be done by storing those points before calculating.
We have to apply sweep line algorithm once for all vertical lines and once for all horizontal lines.
Actually there is a almost same problem which was asked in one of the Codeforces round earlier. Just in that problem, you had to change the part regarding the cases when both the intersection occur at the boundaries. For that as per the question, we can see that at a given point maximum of 2 lines can intersect (you can prove it using contradiction: Suppose 3 lines intersect. All 3 can’t be horizontal or vertical. Without loss of generality assume 2 are horizontal and 1 is vertical, then again no 2 horizontal lines also share a point. Hence, it is not possible). Thus a simply sort of all the points was enough to remove the last condition.
Here is my clean implementation of the solution. Hope the solution is clear and understandable, once the algorithm is clear.
I did the line sweep as mentioned by anshal21 but I used a modified BST instead of segment/BIT tree. Will the segment/BIT tree approach work for higher values of x and y(say 10^9) ??
Actually I am scanning once but storing the required values in a and b just after scanning the values.For calculating vertical lines I am storing the required values in struct array a and for horizontal lines in struct array b.
