[TIOJ] 1401. 功夫城堡

題目連結:http://tioj.infor.org/problems/1401

---

我好廢QQ被雷了才會。
很簡單的可以觀察到垂直跟水平可以分開，那這樣的話問題被轉化成給你一堆線段，你要為每條線段選一個點，使得這些點不能重複。做法很greedy直接從左掃到右邊，然後如果有可以放的就放，然後如果遇到一條線段就把他右界放進去之類的。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
const int N = 100000 + 5;

vector<int> hen[N], zhi[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++){
			hen[i].clear();
			zhi[i].clear();
		}
		bool flag = true;
		for(int i=0;i<n;i++){
			int l, r, u, d; cin>>l>>r>>u>>d;
			hen[l].PB(r);
			zhi[u].PB(d);
		}
		priority_queue<int,vector<int>,greater<int>> pq;
		for(int i=1;i<=n;i++){
			for(auto j: hen[i]) pq.push(j);
			if(!pq.empty()){
				if(pq.top() < i) flag = 0;
				else pq.pop();
			}
		}
		if(!pq.empty()) flag = 0;
		for(int i=1;i<=n;i++){
			for(auto j: zhi[i]) pq.push(j);
			if(!pq.empty()){
				if(pq.top() < i) flag = 0;
				else pq.pop();
			}
		}
		if(!pq.empty()) flag = 0;
		cout<<(flag?"YES":"NO")<<'\n';
	}
	return 0;
}