Codeforces-1008B B. Turn the Rectangles

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 nn (1n105) — the number of rectangles.

Each of the next nn lines contains two integers wiwi and hihi (1wi,hi109) — the width and the height of the ii-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).

Input

3
3 4
4 6
3 5

Output

YES

Input

2
3 4
5 5

Output

NO

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

分析:贪心题·,第一最优解是取第二个小于第一个高的矩形的长边。第二为短边,否则输出NO.

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
  int n=0;
  cin>>n;
  int a,b;
  cin>>a>>b;
  int curr=max(a,b);
  for(int i=1;i<n;i++)
  {
    cin>>a>>b;
        if (curr>=max(a,b)) curr=max(a,b);
        else if (curr>=min(a,b)) curr=min(a,b);
        else
        {
            cout<<"NO"<<endl;
            return 0;
        }
  }
  cout<<"YES"<<endl;
  return 0;
}

注意点:

1.第一次做的时候用了数组存储输入的矩形信息,结果WA在了第五组,后来多方面侦查后发现,我他妈就是个智障,题目给的105的数据量级范围是1-99999,结果我以为最大到一万,开了一万五的数组,WA的原因是数据溢出导致输出结果错误。

2.rectangle和triangle搞混了,还好不影响做题,我个智障得补英语了

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 + 8 =