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




可复制的 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