A. Visiting a Friend

Codeforces

IDCF902A

Time1000ms

Memory256MB

Difficulty—

greedyimplementation

English · Original

Chinese · Translation

Formal · Original

Pig is visiting a friend. Pig's house is located at point 0, and his friend's house is located at point _m_ on an axis. Pig can use teleports to move along the axis. To use a teleport, Pig should come to a certain point (where the teleport is located) and choose where to move: for each teleport there is the rightmost point it can move Pig to, this point is known as the limit of the teleport. Formally, a teleport located at point _x_ with limit _y_ can move Pig from point _x_ to any point within the segment \[_x_; _y_\], including the bounds. <center>![image](https://espresso.codeforces.com/ac5b7c8a91aa8756da17036e40160876c65231c3.png)</center>Determine if Pig can visit the friend using teleports only, or he should use his car. ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 100, 1 ≤ _m_ ≤ 100) — the number of teleports and the location of the friend's house. The next _n_ lines contain information about teleports. The _i_\-th of these lines contains two integers _a__i_ and _b__i_ (0 ≤ _a__i_ ≤ _b__i_ ≤ _m_), where _a__i_ is the location of the _i_\-th teleport, and _b__i_ is its limit. **It is guaranteed that _a__i_ ≥ _a__i_ - 1 for every _i_ (2 ≤ _i_ ≤ _n_)**. ## Output Print "_YES_" if there is a path from Pig's house to his friend's house that uses only teleports, and "_NO_" otherwise. You can print each letter in arbitrary case (upper or lower). [samples] ## Note The first example is shown on the picture below: <center>![image](https://espresso.codeforces.com/97af9c02f6fbd10e07baa36e74770261d93d5c70.png)</center>Pig can use the first teleport from his house (point 0) to reach point 2, then using the second teleport go from point 2 to point 3, then using the third teleport go from point 3 to point 5, where his friend lives. The second example is shown on the picture below: <center>![image](https://espresso.codeforces.com/122f57806a14b001c70f0ae56f5369c9a3867820.png)</center>You can see that there is no path from Pig's house to his friend's house that uses only teleports.

Pig 正在拜访一位朋友。 Pig 的房子位于点 #cf_span[0]，他的朋友的房子位于数轴上的点 #cf_span[m]。 Pig 可以使用传送装置沿数轴移动。要使用传送装置，Pig 必须先到达该传送装置所在的位置，并选择移动到何处：每个传送装置都有一个最远可将 Pig 传送到的点，该点被称为该传送装置的极限。形式上，位于点 #cf_span[x] 且极限为 #cf_span[y] 的传送装置，可以将 Pig 从点 #cf_span[x] 传送到区间 #cf_span[[x; y]] 内的任意点，包括端点。判断 Pig 是否仅通过传送装置即可拜访朋友，还是必须使用汽车。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100, 1 ≤ m ≤ 100]）——传送装置的数量和朋友家的位置。接下来的 #cf_span[n] 行描述了每个传送装置的信息。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[0 ≤ ai ≤ bi ≤ m]），其中 #cf_span[ai] 是第 #cf_span[i] 个传送装置的位置，#cf_span[bi] 是其极限。 *保证对于每个 #cf_span[i]（#cf_span[2 ≤ i ≤ n]），都有 #cf_span[ai ≥ ai - 1]*。如果存在一条仅使用传送装置从 Pig 的家到朋友家的路径，则输出 "_YES_"，否则输出 "_NO_"。你可以以任意大小写形式输出每个字母。第一个示例如下图所示： Pig 可以从家（点 #cf_span[0]）使用第一个传送装置到达点 #cf_span[2]，然后使用第二个传送装置从点 #cf_span[2] 移动到点 #cf_span[3]，再使用第三个传送装置从点 #cf_span[3] 移动到点 #cf_span[5]，即他朋友的家。第二个示例如下图所示：你可以看到，不存在一条仅使用传送装置从 Pig 的家到朋友家的路径。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100, 1 ≤ m ≤ 100]）——传送装置的数量和朋友家的位置。接下来的 #cf_span[n] 行描述了每个传送装置的信息。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[0 ≤ ai ≤ bi ≤ m]），其中 #cf_span[ai] 是第 #cf_span[i] 个传送装置的位置，#cf_span[bi] 是其极限。*保证对于每个 #cf_span[i]（#cf_span[2 ≤ i ≤ n]），都有 #cf_span[ai ≥ ai - 1]*。 ## Output 如果存在一条仅使用传送装置从 Pig 的家到朋友家的路径，则输出 "_YES_"，否则输出 "_NO_"。你可以以任意大小写形式输出每个字母。 [samples] ## Note 第一个示例如下图所示： Pig 可以从家（点 #cf_span[0]）使用第一个传送装置到达点 #cf_span[2]，然后使用第二个传送装置从点 #cf_span[2] 移动到点 #cf_span[3]，再使用第三个传送装置从点 #cf_span[3] 移动到点 #cf_span[5]，即他朋友的家。第二个示例如下图所示：你可以看到，不存在一条仅使用传送装置从 Pig 的家到朋友家的路径。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 100 $, $ 1 \leq m \leq 100 $. Let $ T = \{(a_i, b_i) \mid i \in \{1, \dots, n\}\} $ be a set of teleports, where: - $ a_i \in \mathbb{Z} $ is the location of teleport $ i $, - $ b_i \in \mathbb{Z} $ is its limit, satisfying $ 0 \leq a_i \leq b_i \leq m $, - and $ a_i \geq a_{i-1} $ for all $ i \in \{2, \dots, n\} $. **Constraints** 1. Pig starts at point $ 0 $. 2. Goal is to reach point $ m $. 3. From any point $ x \in [a_i, b_i] $, a teleport $ (a_i, b_i) $ allows movement to any point in $ [a_i, b_i] $. 4. Pig may only use a teleport if he is already at or beyond its location $ a_i $. **Objective** Determine whether there exists a sequence of teleport uses starting from $ 0 $ and ending at $ m $, such that each transition stays within the bounds of some teleport. Equivalently: Let $ r $ be the maximum reachable point starting from $ 0 $. Initialize $ r = 0 $. For each teleport $ (a_i, b_i) $ in order: - If $ a_i > r $, return "NO". - Else, update $ r = \max(r, b_i) $. If $ r \geq m $, return "YES"; otherwise, "NO".

Samples

Input #1

Output #1

YES

Input #2

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "A. Visiting a Friend",
    "description": {
      "content": "Pig is visiting a friend. Pig's house is located at point 0, and his friend's house is located at point _m_ on an axis. Pig can use teleports to move along the axis. To use a teleport, Pig should c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF902A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Pig is visiting a friend.\n\nPig's house is located at point 0, and his friend's house is located at point _m_ on an axis.\n\nPig can use teleports to move along the axis.\n\nTo use a teleport, Pig should c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Pig 正在拜访一位朋友。\n\nPig 的房子位于点 #cf_span[0]，他的朋友的房子位于数轴上的点 #cf_span[m]。\n\nPig 可以使用传送装置沿数轴移动。\n\n要使用传送装置，Pig 必须先到达该传送装置所在的位置，并选择移动到何处：每个传送装置都有一个最远可将 Pig 传送到的点，该点被称为该传送装置的极限。\n\n形式上，位于点 #cf_span[x] 且极限为 #cf_span[y...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 100 $, $ 1 \\leq m \\leq 100 $.  \nLet $ T = \\{(a_i, b_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be a set of teleports, where:  \n- $ a_i \\in \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments