東京大学プログラミングコンテスト2012

H - 区間スケジューリングクエリ


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

N 個の仕事がある. 各仕事 i には開始時刻 IL_i と終了時刻 IR_i が設定されている. 仕事は,開始時刻から終了時刻まで続けて行わなければならず,一人が同時に複数の仕事を行うことはできない. ただし,前の仕事が終了したその時刻に次の仕事を開始することは可能である. 即ち,IR_i = IL_j であるような仕事 i, j は続けて行うことができる.

Q 人の人がいる. 各人 k には仕事を開始できる時刻 QL_k と,仕事を終了していたい時刻 QR_k が定まっている. 各人について,この時間の間で,できるだけ多くの仕事を行わせたい. 人 k は 仕事 iQL_k \leq IL_i かつ IR_i \leq QR_k であれば行うことができる. 同じ仕事を複数の人が行うことになっても構わない.

仕事および人の情報が与えられた時,各人について,最大で何個の仕事を行うことができるかを求めるプログラムを作成せよ.


入力

N Q
IL_1 IR_1
...
IL_N IR_N
QL_1 QR_1
...
QL_Q QR_Q

1 行目に仕事の個数 N, 人の人数 Q が与えられる.

続く N 行の i 行目には仕事 i の開始時刻 IL_i と終了時刻 IR_i が与えられる. 時刻は整数で表される.

続く Q 行の k 行目には人 k の仕事を開始できる時刻 QL_k と仕事を終了していたい時刻 QR_k が与えられる.

出力

各人について,最大で何個の仕事を行うことができるかを表す整数を出力せよ. 即ち,出力は Q 行からなり,k 行目には人 k が最大で何個の仕事を行うことができるかを表す 1 つの整数を出力せよ.

制約

部分点

この問題の判定には,50 点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は追加で以下の条件を満たす.


入力例 1

5 4
0 20
30 40
20 30
10 25
25 40
10 30
0 40
20 40
0 30

入力例 1 に対する出力例

1
3
2
2

Submit提出する