kmjp's blog

競技プログラミング参加記です

yukicoder : No.759 悪くない忘年会にしような!

これ系のテクは最近何度か使った。
https://yukicoder.me/problems/no/759

問題

3次元空間にN個の頂点があり、その座標がX[i],Y[i],Z[i]であるとする。

ある点iが、別の点jに対し軸に平行な直方体(0,0,0)-(X[j],Y[j],Z[j])の内部または辺・面上にありかつjと一致しない場合、iはjの下位互換とする。
他の点の下位互換にならない点を列挙せよ。

解法

EditorialはSegmentTreeを使っているが、Map1個で解くこともできる。

下記の記事にある通り、(0,0)と(X,Y)を対角線とする軸に平行な長方形が多数あるとき、その和集合はmap1個で管理できる。
また、ある頂点がその和集合の内部にあるかどうかもlower_boundで判定できる。
Codeforces #419 Div1 D. Karen and Cards - kmjp's blog

Z座標降順でこの和集合に長方形を加えていくことで、各頂点が他の頂点が成す直方体の和集合の内部にならないか判定しよう。

頂点をZ座標毎にグループ化し、降順に処理していく。
今、Z座標(z+1)まで処理が終わり、次にZ座標がzの頂点群を処理することを考える。
この際、次の順に処理する。

  • 各頂点iに対し、Z座標が(z+1)以上である頂点の下位互換かを判定する。これは前述の和集合の座標のうち、(X[i],Y[i])の右上に来るものがあるかチェックすればよい。
  • 各頂点iに対し、(0,0)-(X[i],Y[i])を前述の和集合に加える。
  • 各頂点iに対し、Z座標がz以上である頂点の下位互換かを判定する。これは前述の和集合の座標のうち、(X[i]+1,Y[i])の右上または(X[i],Y[i]+1)の右上に来るものがあるかチェックすればよい。
int N;
int X[101010],Y[101010],Z[101010];
vector<int> ev[303030];

map<int,int> M;
int ng[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	M[-1]=1<<20;
	M[1<<20]=-1;
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>Z[i];
		ev[Z[i]].push_back(i);
	}
	
	for(i=10000;i>=0;i--) if(ev[i].size()) {
		FORR(e,ev[i]) {
			auto it=M.lower_bound(X[e]);
			if(it->second>=Y[e]) ng[e]=1;
		}
		FORR(e,ev[i]) {
			x=X[e];
			y=Y[e];
			auto k=M.lower_bound(x);
			if(k->second>=y) continue;
			while(prev(M.lower_bound(x))->second<=y) M.erase(prev(M.lower_bound(x)));
			M[x]=y;
		}
		FORR(e,ev[i]) {
			auto it=M.lower_bound(X[e]);
			if(it->second>Y[e]) ng[e]=1;
			it=M.lower_bound(X[e]+1);
			if(it->second>=Y[e]) ng[e]=1;
		}
	}
	
	
	FOR(i,N) if(ng[i]==0) cout<<(i+1)<<endl;
}

まとめ

まぁまぁ簡単に書けたんじゃないかね。