B. Turn the Rectangles

Codeforces

IDCF1008B

Time2000ms

Memory256MB

Difficulty—

greedysortings

English · Original

Chinese · Translation

Formal · Original

There are $n$ rectangles in a row. You can either turn each rectangle by $90$ degrees or leave it as it is. If you turn a rectangle, its width will be height, and its height will be width. Notice that you can turn any number of rectangles, you also can turn all or none of them. **You can not change the order of the rectangles.** Find out if there is a way to make the rectangles go in order of non-ascending height. In other words, after all the turns, a height of every rectangle has to be not greater than the height of the previous rectangle (if it is such). ## Input The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of rectangles. Each of the next $n$ lines contains two integers $w_i$ and $h_i$ ($1 \leq w_i, h_i \leq 10^9$) — the width and the height of the $i$\-th rectangle. ## Output Print "_YES_" (without quotes) if there is a way to make the rectangles go in order of non-ascending height, otherwise print "_NO_". You can print each letter in any case (upper or lower). [samples] ## Note In the first test, you can rotate the second and the third rectangles so that the heights will be _\[4, 4, 3\]_. In the second test, there is no way the second rectangle will be not higher than the first one.

一行中有 $n$ 个矩形。你可以选择将每个矩形旋转 $90$ 度，或者保持原样。如果你旋转一个矩形，它的宽会变成高，高会变成宽。注意，你可以旋转任意数量的矩形，也可以全部旋转或一个都不旋转。*你不能改变矩形的顺序。* 请判断是否存在一种方式，使得所有矩形按非递增高度排列。换句话说，在所有旋转操作之后，每个矩形的高度都不大于前一个矩形的高度（如果存在前一个矩形）。第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 矩形的数量。接下来的 $n$ 行，每行包含两个整数 $w_i$ 和 $h_i$ ($1 lt.eq w_i, h_i lt.eq 10^9$) —— 第 $i$ 个矩形的宽和高。如果存在一种方式使得矩形按非递增高度排列，请输出 "_YES_"（不含引号），否则输出 "_NO_"。你可以以任意大小写形式输出每个字母。在第一个测试用例中，你可以旋转第二个和第三个矩形，使得高度变为 _[4, 4, 3]_。在第二个测试用例中，无法使第二个矩形的高度不大于第一个矩形的高度。 ## Input 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 矩形的数量。接下来的 $n$ 行，每行包含两个整数 $w_i$ 和 $h_i$ ($1 lt.eq w_i, h_i lt.eq 10^9$) —— 第 $i$ 个矩形的宽和高。 ## Output 如果存在一种方式使得矩形按非递增高度排列，请输出 "_YES_"（不含引号），否则输出 "_NO_"。你可以以任意大小写形式输出每个字母。 [samples] ## Note 在第一个测试用例中，你可以旋转第二个和第三个矩形，使得高度变为 _[4, 4, 3]_。在第二个测试用例中，无法使第二个矩形的高度不大于第一个矩形的高度。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of rectangles. For each $ i \in \{1, \dots, n\} $, let $ (w_i, h_i) \in \mathbb{Z}^+ \times \mathbb{Z}^+ $ denote the original width and height of rectangle $ i $. Define the set of possible heights for rectangle $ i $: $$ H_i = \{w_i, h_i\} $$ Let $ s_i \in H_i $ be the chosen height of rectangle $ i $ after optional rotation. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq w_i, h_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 3. The sequence of chosen heights $ (s_1, s_2, \dots, s_n) $ must satisfy: $$ s_1 \geq s_2 \geq \cdots \geq s_n $$ and for each $ i $, $ s_i \in H_i $. **Objective** Determine whether there exists a sequence $ (s_1, \dots, s_n) $ such that $ s_i \in H_i $ for all $ i $ and $ s_1 \geq s_2 \geq \cdots \geq s_n $.

Samples

Input #1

Output #1

YES

Input #2

2
3 4
5 5

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "B. Turn the Rectangles",
    "description": {
      "content": "There are $n$ rectangles in a row. You can either turn each rectangle by $90$ degrees or leave it as it is. If you turn a rectangle, its width will be height, and its height will be width. Notice that",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1008B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $n$ rectangles in a row. You can either turn each rectangle by $90$ degrees or leave it as it is. If you turn a rectangle, its width will be height, and its height will be width. Notice that...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一行中有 $n$ 个矩形。你可以选择将每个矩形旋转 $90$ 度，或者保持原样。如果你旋转一个矩形，它的宽会变成高，高会变成宽。注意，你可以旋转任意数量的矩形，也可以全部旋转或一个都不旋转。*你不能改变矩形的顺序。*\n\n请判断是否存在一种方式，使得所有矩形按非递增高度排列。换句话说，在所有旋转操作之后，每个矩形的高度都不大于前一个矩形的高度（如果存在前一个矩形）。\n\n第一行包含一个整数 $n$ (...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of rectangles.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ (w_i, h_i) \\in \\mathbb{Z}^+ \\times \\mathbb{Z}^+ $ denote the original width and he...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments