시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 81 | 49 | 44 | 59.459% |
あなたは,マトリョーシカ人形を販売する店を開こうとしている.そこで,あなたは 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) が与えら れる.それぞれの組について,事前に届くマトリョーシカ人形を入れ子にして保管したときの,どのマト リョーシカ人形にも収納されていないマトリョーシカ人形の個数の最小値を求めるプログラムを作成せよ.
標準入力から以下のデータを読み込め.
出力は Q 行からなる.j 行目 (1 ≦ j ≦ Q) には,組 (Aj, Bj) について,事前に届くマトリョーシカ人形を 入れ子にして保管したときの,どのマトリョーシカ人形にも収納されていないマトリョーシカ人形の個数 の最小値を出力せよ.
번호 | 배점 | 제한 |
---|---|---|
1 | 11 | N ≤ 10, Q = 1. |
2 | 15 | N ≤ 100, Q = 1. |
3 | 25 | N ≤ 2 000, Q ≤ 2 000. |
4 | 49 | 追加の制約はない. |
7 3 9 5 3 7 10 6 5 10 2 6 10 10 4 1 10 5 3 5 3 9
0 1 2
10 8 14 19 9 16 11 2 7 18 20 16 9 5 10 9 20 6 4 17 13 8 7 14 9 3 9 13 4 19 12 4 19 16 18 10 7 14
3 1 3 5 0 2 1 3