CF1015A.Points in Segments

入门

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a set of nn segments on the axis OxOx, each segment has integer endpoints between 11 and mm inclusive. Segments may intersect, overlap or even coincide with each other. Each segment is characterized by two integers lil_i and rir_i (1≤li≤ri≤m1 \le l_i \le r_i \le m) — coordinates of the left and of the right endpoints.

Consider all integer points between 11 and mm inclusive. Your task is to print all such points that don't belong to any segment. The point xx belongs to the segment [l;r][l; r] if and only if l≤x≤rl \le x \le r.

给你 nn 条位于 OxOx 轴上的线段,每条线段的端点均为 11 到 mm(含)之间的整数。这些线段可能相交、重叠,甚至完全重合。每条线段由两个整数 lil_i 和 rir_i(满足 1≤li≤ri≤m1 \le l_i \le r_i \le m)刻画,分别表示其左端点和右端点的坐标。

考虑 11 到 mm(含)之间的所有整数点。你的任务是输出所有不属于任何线段的点。点 xx 属于线段 [l;r][l; r] 当且仅当 l≤x≤rl \le x \le r。

输入格式

The first line of the input contains two integers nn and mm (1≤n,m≤1001 \le n, m \le 100) — the number of segments and the upper bound for coordinates.

The next nn lines contain two integers each lil_i and rir_i (1≤li≤ri≤m1 \le l_i \le r_i \le m) — the endpoints of the ii-th segment. Segments may intersect, overlap or even coincide with each other. Note, it is possible that li=ril_i=r_i, i.e. a segment can degenerate to a point.

输入的第一行包含两个整数 nn 和 mm(1≤n,m≤1001 \le n, m \le 100)——分别表示线段的数量以及坐标的上界。

接下来的 nn 行,每行包含两个整数 lil_i 和 rir_i(1≤li≤ri≤m1 \le l_i \le r_i \le m)——表示第 ii 条线段的两个端点。这些线段可能相交、重叠,甚至完全重合。注意,可能出现 li=ril_i = r_i 的情况,即一条线段可能退化为一个点。

输出格式

In the first line print one integer kk — the number of points that don't belong to any segment.

In the second line print exactly kk 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 00 in the first line and either leave the second line empty or do not print it at all.

第一行输出一个整数 kk —— 不属于任何线段的点的个数。

第二行按任意顺序恰好输出 kk 个整数 —— 这些不属于任何线段的点。你输出的所有点必须互不相同。

如果不存在这样的点,则在第一行输出单个整数 00,第二行可留空或完全不输出。

输入输出样例

  • 输入#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 11 belongs to the second segment, the point 22 belongs to the first and the second segments and the point 55 belongs to the third segment. The points 33 and 44 do not belong to any segment.

In the second example all the points from 11 to 77 belong to the first segment.

在第一个例子中,点 11 属于第二条线段,点 22 属于第一条和第二条线段,点 55 属于第三条线段。点 33 和 44 不属于任何线段。

在第二个例子中,从 11 到 77 的所有点都属于第一条线段。

输入解题思路,AI测评打分。不知道怎么写?

首页