IEMCO8E - Editorial

Infinity Land
Problem Link :
Data Structures , Sorting
This problem with small coordinates can be solved using partial sums and some easy counting. Let’s carry an array cnt, where cnti will be equal to the number of segments that cover the point with coordinate i. How to calculate cnt in O(n+maxX)?

For each segment (li,ri) let’s add +1 to cnt(li) and −1 to cnt(ri+1). Now build on this array prefix sums and notice that cnt(i) equals the number of segments that cover the point with coordinate i. All the answers can be calculated in O(maxX) in total. So the total complexity of this solution is O(n+maxX).

But in our problem it is too slow to build an entire array cnt. So what should we do? It is obvious that if any coordinate j is not equals some li or some ri+1 then cnt(i)=cnt(i−1). So we do not need carry all the positions explicitly. Let’s carry all li and ri+1 in some logarithmic data structure or let’s use the coordinate compression method.

The coordinate compression method allows us to transform the set of big sparse objects to the set of small compressed objects maintaining the relative order. In our problems let’s make the following things: push all li and ri+1 in vector cval, sort this vector, keep only unique values and then use the position of elements in vector cval instead of original value (any position can be found in O(logn) by binary search or standard methods as lower_bound in C++).

So the first part of the solution works in O(nlogn). Answer can be calculated using almost the same approach as in solution to this problem with small coordinates. But now we know that between two adjacent elements cval(i) and cval(i+1) there is exactly cval(i+1)−cval(i) points with answer equals to cnt(i). So if we will iterate over all pairs of the adjacent elements cval(i) and cval(i+1) and add cval(i+1)−cval(i) to the ans(cnt(i)), we will calculate all the answers in O(n).

So the total complexity of the solution is O(nlogn).

Solution :
Solution to the problem can be found here

1 Like