← 返回题目列表

AtCoder · joisc2016_a

A. 俄罗斯套娃

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

マトリョーシカ人形 - 原题 PDF 第 1 页
原题PDF第1页
マトリョーシカ人形 - 原题 PDF 第 2 页
原题PDF第2页
マトリョーシカ人形 - 原题 PDF 第 3 页
原题PDF第3页
マトリョーシカ人形 - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                       Contest Day 1 – Matryoshka


              マトリョーシカ人形(Matryoshka)



 あなたは,マトリョーシカ人形を販売する店を開こうとしている.そこで,あなたはN 個のマトリョーシ
カ人形を工場に注文した.これらには1 からN までの番号が付けられている.このうちi 番目(1 ≦i ≦N)
のマトリョーシカ人形は,底面の直径Ri cm で高さHi cm の,中が空洞の直円柱とみなすことができる.
 マトリョーシカ人形は入れ子にして保管することができる.それぞれのマトリョーシカ人形は,底面の
直径と高さがともにより小さい他のマトリョーシカ人形を1 つだけ収納することが出来る.収納されるマ
トリョーシカ人形は,他のマトリョーシカ人形を収納していてもよい.
 ある日,マトリョーシカ人形を注文した工場から連絡が届いた.注文したN 個のマトリョーシカ人形は
すべてを一度に用意することはできないので,N 個のマトリョーシカ人形のうち底面の直径がA cm 以上で
あり,高さがB cm 以下であるものすべてが事前に届くそうだ.
  A, B の値は急に変更されるかもしれない.そこで,あなたは,Q 個の組(Aj, Bj) (1 ≦j ≦Q) のそれぞれ
に対して,事前に届くマトリョーシカ人形を入れ子にして保管したときの,どのマトリョーシカ人形にも
収納されていないマトリョーシカ人形の個数の最小値をあらかじめ求めておくことにした.


課題

 それぞれのマトリョーシカ人形の底面の直径と高さの情報と,Q 個の組(Aj, Bj) (1 ≦j ≦Q) が与えら
れる.それぞれの組について,事前に届くマトリョーシカ人形を入れ子にして保管したときの,どのマト
リョーシカ人形にも収納されていないマトリョーシカ人形の個数の最小値を求めるプログラムを作成せよ.


入力

 標準入力から以下のデータを読み込め.

   • 1 行目には,整数N, Q が空白を区切りとして書かれている.これは,注文したマトリョーシカ人形
   の個数がN 個であり,A, B の値の組がQ 個与えられることを表す.

   • 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ri, Hi が空白を区切りとして書かれている.これは,
         i 番目のマトリョーシカ人形は,底面の直径がRi cm で高さがHi cm であることを表す.

   • 続くQ 行のうちのj 行目(1 ≦j ≦Q) には,整数Aj, Bj が空白を区切りとして書かれている.


出力

 出力はQ 行からなる.j 行目(1 ≦j ≦Q) には,組(Aj, Bj) について,事前に届くマトリョーシカ人形を
入れ子にして保管したときの,どのマトリョーシカ人形にも収納されていないマトリョーシカ人形の個数
の最小値を出力せよ.




                   マトリョーシカ人形– 1 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                       Contest Day 1 – Matryoshka


制限

 すべての入力データは以下の条件を満たす.

   • 1 ≦N ≦200 000.

   • 1 ≦Q ≦200 000.

   • 1 ≦Ri ≦1 000 000 000 (1 ≦i ≦N).

   • 1 ≦Hi ≦1 000 000 000 (1 ≦i ≦N).

   • 1 ≦Aj ≦1 000 000 000 (1 ≦j ≦Q).

   • 1 ≦Bj ≦1 000 000 000 (1 ≦j ≦Q).


小課題

小課題1 [11 点]

 以下の条件を満たす.

   • N ≦10.

   • Q = 1.


小課題2 [15 点]

 以下の条件を満たす.

   • N ≦100.

   • Q = 1.


小課題3 [25 点]

 以下の条件を満たす.

   • N ≦2 000.

   • Q ≦2 000.


小課題4 [49 点]

 追加の制約はない.



                   マトリョーシカ人形– 2 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                       Contest Day 1 – Matryoshka


入出力例

  入力例1        出力例1
   7 3                  0
   9 5                  1
   3 7                  2
   10 6
   5 10
   2 6
   10 10
   4 1
   10 5
   3 5
   3 9


   • (A, B) = (10, 5) のとき,底面の直径が10 cm 以上で高さが5 cm 以下であるマトリョーシカ人形は1
   つも存在しないので,0 を出力する.

   • (A, B) = (3, 5) のとき,底面の直径が3 cm 以上で高さが5 cm 以下であるマトリョーシカ人形,すなわ
   ち1 番目,7 番目のマトリョーシカ人形が届く.7 番目のマトリョーシカ人形は1 番目のマトリョー
   シカ人形の中に収納することができる.どのマトリョーシカ人形にも収納されていないマトリョーシ
   カ人形の個数の最小値は1 である.

   • (A, B) = (3, 9) のとき,底面の直径が3 cm 以上で高さが9 cm 以下であるマトリョーシカ人形,すな
   わち1 番目,2 番目,3 番目,7 番目のマトリョーシカ人形が届く.この場合,7 番目のマトリョー
   シカ人形を1 番目のマトリョーシカ人形の中に収納して,1 番目のマトリョーシカ人形を3 番目のマ
   トリョーシカ人形の中に収納することができる.どのマトリョーシカ人形にも収納されていないマト
   リョーシカ人形の個数の最小値は2 である.





                   マトリョーシカ人形– 3 / 4

Japanese Olympiad in Informatics 2015/2016
                                                        Spring Training Camp/Qualifying Trial
                                            March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                   Contest Day 1 – Matryoshka



入力例2        出力例2
10 8                 3
14 19                1
9 16                 3
11 2                 5
7 18                 0
20 16                2
9 5                  1
10 9                 3
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14





                 マトリョーシカ人形– 4 / 4