CSAcademy Round #12 : C. Independent Rectangles

遅れて参加したり途中抜けたりしたけど、Div2ということで一応全完。
https://csacademy.com/contest/round-12/#task/independent-rectangles

問題

N個の長方形の幅・高さが与えられる。
独立した長方形とは、幅も高さも自身より大きな長方形がないものを示す。
(回転は許可しない)

独立した長方形はN個中いくつあるか。

解法

長方形を高さ順にグループ化し、高さの高い順に処理しよう。

bitを用いて、自身より高い長方形について、ある幅までの長方形の数を高速に数えられるようにすればよい。
高さ順にbitに長方形を入れているので、既にbitに自身の幅より大きな幅の長方形があるなら、高さでも負けることになり、独立ではないことがわかる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,21> bt;

int N;
vector<int> H[1010100];


void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		H[x].push_back(y);
	}
	
	int ret=0;
	for(i=1000000;i>=1;i--) {
		FORR(r,H[i]) if(bt(1000001)-bt(r)==0) ret++;
		FORR(r,H[i]) bt.add(r,1);
	}
	cout<<ret<<endl;
}

まとめ

回転有だともう少し難しい…？