31641번 - 感染シミュレーション (Infection Simulation) 서브태스크다국어

문제

EGOI 食堂には昨日 N 人の客が来店した. 客には 1 から N までの番号が付けられており,客 i (1 ≦ i ≦ N) の来店時刻は L_i,退店時刻は R_i であった. そして今日,客のうち 1 人が,現在 JOI 国で流行している新型の感染症 X に感染した状態で来店したことが明らかになった.

感染症 X の感染しづらさは整数 x で表される. 具体的には,1 ≦ i ≦ N について,客 i が 1 人以上の感染者と同時に食堂内にいた時間の累計が x 以上となったタイミングで,客 i は新たに感染者となる.

さて,JOI 国では厳格な感染症対策を行っているため,感染者数を正確に把握しなければならない. しかし困ったことに,誰が感染症 X に感染したかの情報は得られておらず,感染しづらさを表す整数 x も分かっていない.

そこで EGOI 食堂の店長である理恵さんは,Q 個のシナリオについて,最終的に何人の客が感染するのかを求めることにした. j 番目 (1 ≦ j ≦ Q) のシナリオでは,最初の感染者が客 P_j のみであり,感染症 X の感染しづらさが X_j である.

来店した客およびシナリオの情報が与えられたとき,それぞれのシナリオにおける最終的な感染者数を出力するプログラムを作成せよ. ただし,退店時刻ちょうどに感染した場合も,感染者数に含めるものとする. また,感染症 X に一度感染した客が感染者でなくなることは考えないものとする.

입력

入力は以下の形式で与えられる.

N
L1 R1
L2 R2
...
LN RN
Q
P1 X1
P2 X2
...
PQ XQ

출력

Q 行出力せよ.j 行目 (1 ≦ j ≦ Q) には,j 番目のシナリオにおける最終的な感染者数を出力せよ.

제한

• 1 ≦ N ≦ 100 000.
• 0 ≦ L_i < R_i ≦ 10⁹ (1 ≦ i ≦ N).
• 1 ≦ Q ≦ 100 000.
• 1 ≦ P_j ≦ N (1 ≦ j ≦ Q).
• 1 ≦ X_j ≦ 10⁹ (1 ≦ j ≦ Q).
• 入力される値はすべて整数である.

서브태스크

힌트