TopCoder

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

User's AC Ratio

87.2% (68/78)

Submission's AC Ratio

34.6% (99/286)

Tags

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 1

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

Sample Output 1

YES

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 8000 65536 262144 1
1 8000 65536 262144 2