1468

5000個程度の長方形の座標が与えられるので、他のいずれかの中に完全に含まれるものの個数を答えよ、という問題。

自明解は5000^2で、多分間に合わないと信じる。logNを出す必要があるので、ソートか何かかなぁ、という感じ。

取り敢えず、左から順番になめて、自分より左の人を探す。ソートするのにO(NlogN)で、なめるのはO(N)なので、問題ない。これを4方向にやるのも問題なさそう。問題は4方向ともに存在する人を探さないといけないこと。5000個のboolean値で持つとすると、5000*5000*sizeof(boolean)になるので10MBは超過してしまう...。仕方がないので、longに埋め込んで5000*80*sizeof(long)=3.2MBくらいに押し込んでやった。自分自身の中に入る判定になるので、それだけ除外して、0じゃないlong値があれば4方向とも存在する人がいる、となる。