olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

魚の生息範囲(13予選5)

N種類の魚がいて、それぞれの生息範囲が直方体で与えられる。

同時にK種類の魚が存在しうる領域の体積を求めよという問題。

まず、座標の範囲が0~1000000と非常に大きいにもかかわらず、魚の種類は最大でも50なので無駄っぽい。なのでそれぞれについてソートした後、番号をつける。すると座標は最大で100になる。

すると、100^3の各領域に関して魚が何種類存在するか調べられるので、その体積の総和を出力する。

計算量はO(N^4)(多分)

難易度は7程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2321058#1