TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

88.9% (24/27)

Submission's AC Ratio

36.4% (36/99)

Description

請問你能不能在一個 N*N 的棋盤上放置 N 個城堡(rook),使得他們不能互相攻擊?(也就是說,任兩隻城堡不能在棋盤的同一行或同一列)

這個問題很簡單吧?

但是,現在這些城堡為了鍛鍊功夫,他們被限制在不盡相同的矩形範圍裡面。

請你判斷他們能不能全部放到棋盤上,滿足條件,並且不能互相攻擊?

Input Format

輸入檔可能包含多筆測試資料,以EOF結束輸入。

每一筆測試資料的第一列有一個正整數N(1<=N<=100,000),代表棋盤大小。

接下來有N列第i列代表對第i個城堡的限制:Li,Ri,Di,Ui。(Li<=Ri, Di<=Ui)
分別代表矩形範圍的左、右、上、下界。

Output Format

對於每筆測試資料,存在一種滿足條件的放置城堡方式,請輸出YES,否則輸出NO。

Sample Input

4
1 2 1 3
2 4 2 4
3 4 1 2
1 4 2 2

Sample Output

YES

Hints

抱歉...來不及想題目敘述了XDrz...

Problem Source

原TIOJ1401 / 快樂暑假營第四次練習比賽。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 8000 65536 262144
1 8000 65536 262144