J. Segments

Codeforces

IDCF953J

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

There is a straight line colored in white. _n_ black segments are added on it one by one. After each segment is added, determine the number of connected components of black segments (i. e. the number of black segments in the union of the black segments). In particular, if one segment ends in a point _x_, and another segment starts in the point _x_, these two segments belong to the same connected component. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 200 000) — the number of segments. The _i_\-th of the next _n_ lines contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_ < _r__i_ ≤ 109) — the coordinates of the left and the right ends of the _i_\-th segment. The segments are listed in the order they are added on the white line. ## Output Print _n_ integers — the number of connected components of black segments after each segment is added. [samples] ## Note In the first example there are two components after the addition of the first two segments, because these segments do not intersect. The third added segment intersects the left segment and touches the right segment at the point 4 (these segments belong to the same component, according to the statements). Thus the number of connected components of black segments is equal to 1 after that.

有一条白色直线。依次向其上添加 #cf_span[n] 个黑色线段。在每个线段添加后，确定黑色线段的连通分量数量（即黑色线段并集中的线段段数）。特别地，如果一个线段的右端点为 #cf_span[x]，另一个线段的左端点也为 #cf_span[x]，则这两个线段属于同一个连通分量。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——线段的数量。接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li < ri ≤ 109]）——第 #cf_span[i] 个线段的左端点和右端点坐标。线段按添加顺序列出。请输出 #cf_span[n] 个整数——每个线段添加后，黑色线段的连通分量数量。在第一个例子中，前两个线段添加后有两个连通分量，因为它们不相交。第三个添加的线段与左侧线段相交，并在点 #cf_span[4] 处接触右侧线段（根据题意，这两个线段属于同一连通分量）。因此，此时黑色线段的连通分量数量为 #cf_span[1]。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——线段的数量。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li < ri ≤ 109]）——第 #cf_span[i] 个线段的左端点和右端点坐标。线段按添加顺序列出。 ## Output 请输出 #cf_span[n] 个整数——每个线段添加后，黑色线段的连通分量数量。 [samples] ## Note 在第一个例子中，前两个线段添加后有两个连通分量，因为它们不相交。第三个添加的线段与左侧线段相交，并在点 #cf_span[4] 处接触右侧线段（根据题意，这两个线段属于同一连通分量）。因此，此时黑色线段的连通分量数量为 #cf_span[1]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of segments. Let $ S_i = [l_i, r_i] \subset \mathbb{R} $ be the $ i $-th closed interval (segment) added, with $ 1 \leq l_i < r_i \leq 10^9 $, for $ i = 1, \dots, n $. Let $ C_i $ denote the number of connected components of the union $ \bigcup_{j=1}^i S_j $ after the $ i $-th segment is added. **Constraints** 1. $ 1 \leq n \leq 200{,}000 $ 2. For all $ i \in \{1, \dots, n\} $: $ 1 \leq l_i < r_i \leq 10^9 $ **Objective** For each $ i \in \{1, \dots, n\} $, compute $ C_i $, where two segments are in the same connected component if their closures intersect (i.e., $ [a,b] \cap [c,d] \neq \emptyset $ implies they are connected; in particular, $ b = c $ suffices for connection). The output is the sequence $ C_1, C_2, \dots, C_n $.

Samples

Input #1

Output #1

1 2 1

Input #2

Output #2

1 2 3 4 5 4 3 2 1

API Response (JSON)

{
  "problem": {
    "name": "J. Segments",
    "description": {
      "content": "There is a straight line colored in white. _n_ black segments are added on it one by one. After each segment is added, determine the number of connected components of black segments (i. e. the number",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF953J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a straight line colored in white. _n_ black segments are added on it one by one.\n\nAfter each segment is added, determine the number of connected components of black segments (i. e. the number...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有一条白色直线。依次向其上添加 #cf_span[n] 个黑色线段。\n\n在每个线段添加后，确定黑色线段的连通分量数量（即黑色线段并集中的线段段数）。\n\n特别地，如果一个线段的右端点为 #cf_span[x]，另一个线段的左端点也为 #cf_span[x]，则这两个线段属于同一个连通分量。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——线段的数...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of segments.  \nLet $ S_i = [l_i, r_i] \\subset \\mathbb{R} $ be the $ i $-th closed interval (segment) added, with $ 1 \\leq l_i < r_i \\leq 10^9...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments