prithivMLmods/Coder-Stat

1 2 3 4<H1>魚の生息範囲 (Fish) </H1>5<br/>6 7<h2>  問題</h2>8<p>9オーストラリア大陸の西には，広いインド洋が広がっている．海洋研究者である JOI 氏は，インド洋に生息しているある N 種類の魚の性質について研究している．10</p>11 12<p>13それぞれの魚の種類に対して，海の中に直方体状の生息範囲が定まっている．魚は境界も含めて生息範囲の中のどの場所にも移動できるが，生息範囲の外に出ることは決してない．海の中の点は，3 つの実数 (x, y, d) によって表される： (x, y, d) は，上空から見たときにある地点を基準にして東に x，北に y 進んだ位置であり，海面からの深さが d の点を表す．ただし，海面は平面であるとする．14</p>15 16<p>17JOI 氏は，K 種類以上の魚の生息範囲が重なる場所がどのくらいあるかを知りたい．そのような場所全体の体積を求めるプログラムを作成せよ．18</p>19 20<h2>  入力</h2>21<p>22入力は 1 + N 行からなる．23</p>24 25<p>261 行目には，2 つの整数 N, K (1 ≦ K ≦ N ≦ 50) が空白を区切りとして書かれている．これは，魚が N 種類であり，K 種類以上の魚の生息範囲が重なる場所の体積を求めたいことを表す．27</p>28 29<p>30続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，6 つの整数 X<sub>i,1</sub>, Y<sub>i,1</sub>, D<sub>i,1</sub>, X<sub>i,2</sub>, Y<sub>i,2</sub>, D<sub>i,2</sub> (0 ≦ X<sub>i,1</sub> ＜ X<sub>i,2</sub> ≦ 1000000 (= 10<sup>6</sup>)，0 ≦ Y<sub>i,1</sub> ＜ Y<sub>i,2</sub> ≦ 1000000 (= 10<sup>6</sup>)，0 ≦ D<sub>i,1</sub> ＜ D<sub>i,2</sub> ≦ 1000000 (= 10<sup>6</sup>)) が書かれている．これは，i 種類目の魚の生息範囲が31 328 点 (X<sub>i,1</sub>, Y<sub>i,1</sub>, D<sub>i,1</sub>), (X<sub>i,2</sub>, Y<sub>i,1</sub>, D<sub>i,1</sub>), (X<sub>i,2</sub>, Y<sub>i,2</sub>, D<sub>i,1</sub>), (X<sub>i,1</sub>, Y<sub>i,2</sub>, D<sub>i,1</sub>), (X<sub>i,1</sub>, Y<sub>i,1</sub>, D<sub>i,2</sub>), (X<sub>i,2</sub>, Y<sub>i,1</sub>, D<sub>i,2</sub>), (X<sub>i,2</sub>, Y<sub>i,2</sub>, D<sub>i,2</sub>), (X<sub>i,1</sub>, Y<sub>i,2</sub>, D<sub>i,2</sub>) を頂点とする直方体であることを表す．33</p>34 35<h2>  出力</h2>36<p>37K 種類以上の魚の生息範囲が重なる場所全体の体積を 1 行で出力せよ．38</p>39 40<h2>  入出力例</h2>41 42 43<h3>入力例 1</h3>44 45 46  <pre>473 24830 50 0 50 70 1004910 20 20 70 90 605040 60 20 90 90 7051</pre>52 53<h3>出力例 1</h3>54   <pre>554900056</pre>57 58<p>59入出力例 1 において，例えば，点 (45, 65, 65) は 1 種類目の魚と 3 種類目の魚の生息範囲であるので，条件を満たす場所である．一方，点 (25, 35, 45) は 2 種類目の魚のみの生息範囲であるので，条件を満たす場所ではない．また，魚の生息範囲は下の図のようになっている．点 O は海面上の基準の地点を表す．60</p>61<center>62	<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_2013-yo-t5-fig01">63</center>64 65<br/>66 67<h3>入力例 2</h3>  68  <pre>691 1700 0 0 1000000 1000000 100000071</pre>72 73<h3>出力例 2</h3>74 75   <pre>76100000000000000000077</pre>78 79 80<div class="source">81<p class="source">82問題文と自動審判に使われるデータは、<a href="http://www.ioi-jp.org">情報オリンピック日本委員会</a>が作成し公開している問題文と採点用テストデータです。83</p>84</div>85