High-Speed Railway
Time limit1sMemory limit128 MB
Count subsets of interval-graph vertices forming a vertex cover of the interval overlap graph, modulo a given number.
- Level
Medium7 of 10
- Topics
- Intervals, Dynamic programming, Combinatorics
- Solved
- No attempts yet
Problem
A high-speed railway test track can be represented as a straight line. Several robots are installed on the track, and each robot is responsible for one continuous inspection interval. If the inspection intervals of two robots overlap, those two robots must exchange a large amount of data, so at least one of them must be equipped with a special data-processing device.
Suppose there are four robots a, b, c, and d as shown below. The intervals of a and b overlap, so at least one of them needs the device. The same condition must also hold for b and c, b and d, and c and d.
There may be many valid ways to attach the devices. In the figure above, attaching devices to all four robots is valid, and attaching them only to b and c is also valid. The seven valid choices are {a, b, c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {b, d}, and {b, c}.
Given the inspection intervals of the robots, write a program that counts the number of ways to attach devices so that for every overlapping pair of robots, at least one of the two has a device.
Input
The first line contains the number of robots N. (1 <= N <= 100,000)
Each of the next N lines contains two integers: the left endpoint and the right endpoint of one robot's inspection interval.
All coordinates are integers between 0 and 10,000,000, inclusive. The left endpoint of every interval is smaller than its right endpoint. All interval endpoint coordinates are distinct.
Output
Print the number of valid ways to attach the data-processing devices.
If the number of ways is at least 20,070,713, print its remainder after division by 20,070,713. Be careful that overflow may occur during the calculation.