Line Overlap Problem

Calculating the overlapping of line segments is the fundamental problem of computational geometry. In this problem, we consider the simplified line overlap problem – how to calculate the overlapping length of horizontal line segments.

In this problem, all horizontal lines have no y-coordinate, and they can be regarded to have the same y-coordinate. Thus the overlapping check can be achieved by only examining the x-coordinates of two endpoints of every line segment. You have to identify all two line pairs with overlap and sum up the total overlapping length. For example, there are three line segments and any two line segments overlap. Thus you have to find three overlapping lengths and then sum up these three overlapping lengths. Two-loop codes can simply solve this problem, but its time complexity is O(n2), where n is the number of line segments. The runtime will increase substantially as n increases. The time complexity of the optimal solution to this problem is O(nlogn). All benchmarks in this contest can be solved within 0.156 second on the contest platform. Please design an algorithm to calculate the overlapping length of a horizontal line set and guarantee to solve each benchmark within 2 seconds (including 2 seconds). Any test for a benchmark over 2 seconds is regarded to fail.

Input

The input consists of N (N < 200000) datasets representing horizontal lines, followed by a line which contains only a single ‘.’ (period). There are two integers i and j in a line, where the first integer i (i < 100000) is the x-coordinate of left endpoint and the second integer j (j < 100000) is the x-coordinate of right endpoint. Two integers are separated by space character. Notably, the number of space characters is not fixed, do not use space-sensitive instruction to read input file.

75  325
5  120 
100  255
325  500
.

220