[TIOJ 1401] 功夫城堡

作法：

因為一隻城堡影響的是和他同行同列的，所以可以把問題分解成兩個一維上的小問題，也就是給定端點位於 1 ~ n 的 n 條線段，問是否能在每個線段裡都取一個點，使得取的每個點都不同。

而這就可以用貪心做了，考慮左端點在 1 的線段們，我們要決定哪一條線段取 1 ，而會發現讓右端點最左邊的那條線段取 1 是最好的。再來決定要選哪一條線段取 2 ，這次的候選人剩剛剛左端點在 1 的且沒被選到的，還有新的左端點在 2 的線段，這時一樣是取右端點最左邊的那條線段是最好的，也就是左端點在之後的判斷裡沒有用了，於是我們只要維護右端點候選人還剩哪些，每次 pop 出最小的那個就好了。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mkp(x,y) make_pair(x,y)
using namespace std;
const int maxn=100000+10 ;
 
pii x[maxn],y[maxn] ;
int n ;
map<int,int> mp ;
 
bool solve(pii *a)
{
    sort(a+1,a+n+1) ;
    mp.clear() ;
    for(int i=1,j=1;i<=n;i++)
    {
        while(j<=n && a[j].F<=i) mp[a[j].S]++ , j++ ;
        auto it=mp.begin() ;
        if(it->F < i) return 0 ;
        if(!(--it->S)) mp.erase(it) ;
    }
    return 1 ;
}
 
main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d%d%d%d",&x[i].F,&x[i].S,&y[i].F,&y[i].S) ;
        if(!solve(x) || !solve(y)) printf("NO\n") ;
        else printf("YES\n") ;
    }
}