A11900. Points in Segments
编程题
普及/提高-
知识点
题目描述
You are given a set of $n$ segments on the axis $Ox$ , each segment has integer endpoints between $1$ and $m$ inclusive. Segments may intersect, overlap or even coincide with each other. Each segment is characterized by two integers $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le m$ ) — coordinates of the left and of the right endpoints.
Consider all integer points between $1$ and $m$ inclusive. Your task is to print all such points that don't belong to any segment. The point $x$ belongs to the segment $[l; r]$ if and only if $l \le x \le r$ .
Consider all integer points between $1$ and $m$ inclusive. Your task is to print all such points that don't belong to any segment. The point $x$ belongs to the segment $[l; r]$ if and only if $l \le x \le r$ .
输入格式
The first line of the input contains two integers $n$ and $m$ ( $1 \le n, m \le 100$ ) — the number of segments and the upper bound for coordinates.
The next $n$ lines contain two integers each $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le m$ ) — the endpoints of the $i$ -th segment. Segments may intersect, overlap or even coincide with each other. Note, it is possible that $l_i=r_i$ , i.e. a segment can degenerate to a point.
The next $n$ lines contain two integers each $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le m$ ) — the endpoints of the $i$ -th segment. Segments may intersect, overlap or even coincide with each other. Note, it is possible that $l_i=r_i$ , i.e. a segment can degenerate to a point.
输出格式
In the first line print one integer $k$ — the number of points that don't belong to any segment.
In the second line print exactly $k$ integers in any order — the points that don't belong to any segment. All points you print should be distinct.
If there are no such points at all, print a single integer $0$ in the first line and either leave the second line empty or do not print it at all.
In the second line print exactly $k$ integers in any order — the points that don't belong to any segment. All points you print should be distinct.
If there are no such points at all, print a single integer $0$ in the first line and either leave the second line empty or do not print it at all.
输入输出样例
输入 #1
3 5 2 2 1 2 5 5
输出 #1
2 3 4
输入 #2
1 7 1 7
输出 #2
0
说明/提示
In the first example the point $1$ belongs to the second segment, the point $2$ belongs to the first and the second segments and the point $5$ belongs to the third segment. The points $3$ and $4$ do not belong to any segment.
In the second example all the points from $1$ to $7$ belong to the first segment.
In the second example all the points from $1$ to $7$ belong to the first segment.