1008B.md (1544B)
1 Source: https://codeforces.com/problemset/problem/1008/B 2 3 B. Turn the Rectangles 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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). 24 25 Input 26 27 The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of rectangles. 28 29 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. 30 31 Output 32 33 Print "YES" (without quotes) if there is a way to make the rectangles go in order of non-ascending height, otherwise print "NO". 34 35 You can print each letter in any case (upper or lower). 36 37 Examples 38 39 Input 40 41 ``` 42 3 43 3 4 44 4 6 45 3 5 46 ``` 47 48 Output 49 50 ``` 51 YES 52 ``` 53 54 Input 55 56 ``` 57 2 58 3 4 59 5 5 60 ``` 61 62 Output 63 64 ``` 65 NO 66 ``` 67 68 Note 69 70 In the first test, you can rotate the second and the third rectangles so that the heights will be [4, 4, 3]. 71 72 In the second test, there is no way the second rectangle will be not higher than the first one.