CF1008B Turn the Rectangles

    • 52通过
    • 72提交
  • 题目来源 CodeForces 1008B
  • 评测方式 RemoteJudge
  • 标签
  • 难度 普及-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给你n个长方形,问你能否通过任意多次旋转,在不改变他们的相对顺序的情况下让他们的高度形成一个不上升序列。

    题目描述

    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).

    输入输出格式

    输入格式:

    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.

    输出格式:

    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).

    输入输出样例

    输入样例#1: 复制
    3
    3 4
    4 6
    3 5
    
    输出样例#1: 复制
    YES
    
    输入样例#2: 复制
    2
    3 4
    5 5
    
    输出样例#2: 复制
    NO
    

    说明

    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.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。