A. Points in Segments

Codeforces

IDCF1015A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

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$. ## Input 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. ## Output 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. [samples] ## Note 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.

给定数轴 $O x$ 上的 $n$ 个线段，每个线段的端点均为介于 $1$ 到 $m$ 之间的整数。线段之间可能相交、重叠甚至完全重合。每个线段由两个整数 $l_i$ 和 $r_i$（$1 lt.eq l_i lt.eq r_i lt.eq m$）表示，分别为左端点和右端点。考虑所有介于 $1$ 到 $m$ 之间的整数点。你的任务是输出所有不属于任何线段的点。点 $x$ 属于线段 $[ l \; r ]$ 当且仅当 $l lt.eq x lt.eq r$。输入的第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 100$），分别表示线段的数量和坐标的上界。接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 lt.eq l_i lt.eq r_i lt.eq m$），表示第 $i$ 个线段的端点。线段之间可能相交、重叠甚至完全重合。注意，可能存在 $l_i = r_i$，即线段可能退化为一个点。第一行输出一个整数 $k$ —— 不属于任何线段的点的数量。第二行输出恰好 $k$ 个整数（顺序任意）—— 所有不属于任何线段的点。你输出的所有点必须互不相同。如果不存在这样的点，则第一行仅输出整数 $0$，第二行可以留空，或完全不输出。 ## Input 输入的第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 100$），分别表示线段的数量和坐标的上界。接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 lt.eq l_i lt.eq r_i lt.eq m$），表示第 $i$ 个线段的端点。线段之间可能相交、重叠甚至完全重合。注意，可能存在 $l_i = r_i$，即线段可能退化为一个点。 ## Output 第一行输出一个整数 $k$ —— 不属于任何线段的点的数量。第二行输出恰好 $k$ 个整数（顺序任意）—— 所有不属于任何线段的点。你输出的所有点必须互不相同。如果不存在这样的点，则第一行仅输出整数 $0$，第二行可以留空，或完全不输出。 [samples] ## Note 在第一个例子中，点 $1$ 属于第二个线段，点 $2$ 属于第一个和第二个线段，点 $5$ 属于第三个线段。点 $3$ 和 $4$ 不属于任何线段。在第二个例子中，从 $1$ 到 $7$ 的所有点都属于第一个线段。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 100 $. Let $ S = \{ [l_i, r_i] \mid i \in \{1, \dots, n\} \} $ be a set of closed integer intervals, where $ 1 \leq l_i \leq r_i \leq m $ for all $ i $. Let $ U = \{1, 2, \dots, m\} $ be the universal set of integer points. **Constraints** For each segment $ [l_i, r_i] \in S $: - $ l_i, r_i \in \mathbb{Z} $ - $ 1 \leq l_i \leq r_i \leq m $ **Objective** Compute the set $ R = U \setminus \bigcup_{i=1}^n [l_i, r_i] $, i.e., the set of integer points in $ \{1, \dots, m\} $ not covered by any segment. Output: - The cardinality $ k = |R| $, - The elements of $ R $, in any order, if $ k > 0 $.

Samples

Input #1

Output #1

2
3 4

Input #2

1 7
1 7

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Points in Segments",
    "description": {
      "content": "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 i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1015A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定数轴 $O x$ 上的 $n$ 个线段，每个线段的端点均为介于 $1$ 到 $m$ 之间的整数。线段之间可能相交、重叠甚至完全重合。每个线段由两个整数 $l_i$ 和 $r_i$（$1 lt.eq l_i lt.eq r_i lt.eq m$）表示，分别为左端点和右端点。\n\n考虑所有介于 $1$ 到 $m$ 之间的整数点。你的任务是输出所有不属于任何线段的点。点 $x$ 属于线段 $[ l \\...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 100 $.  \nLet $ S = \\{ [l_i, r_i] \\mid i \\in \\{1, \\dots, n\\} \\} $ be a set of closed integer intervals, where $ 1 \\leq l_i \\leq r...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments