Codeforces Round #497 (Div. 2)--B. Turn the Rectangles

B. Turn the Rectangles
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are nn rectangles in a row. You can either turn each rectangle by 9090 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 (1n1051≤n≤105) — the number of rectangles.

Each of the next nn lines contains two integers wiwi and hihi (1wi,hi1091≤wi,hi≤109) — 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).

Examples
input
Copy
3
3 4
4 6
3 5
output
Copy
YES
input
Copy
2
3 4
5 5
output
Copy
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.

题意:有很多个矩形,可以任意旋转(长高可以相互转换)。顺序不可变, 问有没有可以不升序排的方法,有就yes , 无就no。

我的蠢代码(被hacked掉了)

#include <stdio.h>
#include <iostream>
#include <map>
#include <bits/stdc++.h>
using namespace std;
struct node
{
	int l ;
	int r;
}s[100005];
int main()
{
	int t , a , b , n;
	int flag = 0;
	scanf("%d" , &n);
for(int i = 0 ; i < n ; i++)
{
	scanf("%d %d" , &s[i].l , &s[i].r);
}
for(int i = 0 ; i < n-1 ; i++)
{
	if(s[i+1].l <= s[i].l ||s[i+1].l <= s[i].r ||s[i+1].r <= s[i].l ||s[i+1].r <= s[i].r )
	{
		continue;
	}
	else
	{
		flag = 1;
	}
}
if(flag == 1)
{
	printf("NO\n");
	
}
else
{
	printf("YES\n");
}
	return 0;
}
可以AC的代码
#include <stdio.h>
#include <iostream>
#include <map>
#include <bits/stdc++.h>
using namespace std;
struct node
{
	int l ;
	int r;
}s[100005];
int main()
{
	int t , a , b , n;
	int flag = 0;
	scanf("%d" , &n);
for(int i = 0 ; i < n ; i++)
{
	scanf("%d %d" , &s[i].l , &s[i].r);
}
int PP = max(s[0].l,s[0].r);
for(int i = 0 ; i < n ; i++)
{
	int MIN = min(s[i].l,s[i].r);
	int MAX = max(s[i].l,s[i].r);
	if(PP >= MAX)
		{
			PP = MAX;
		}
		else if(PP >= MIN)
		{
			PP = MIN;
		}
		else if(PP < MIN)
		{
			flag = 1;
			break;
			
		}
}
if(flag == 1)
{
	printf("NO\n");
	
}
else
{
	printf("YES\n");
}
	return 0;
}


全部评论

相关推荐

宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
06-10 21:15
门头沟学院 Java
宁阿:好多这种没🧠的公司,他们估计都不知道毕业的人不能给安排实习岗
实习吐槽大会
点赞 评论 收藏
分享
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务