AT_joig2024_f 感染シミュレーション (Infection Simulation)

EGOI 食堂には昨日 $ N $ 人の客が来店した． 客には $ 1 $ から $ N $ までの番号が付けられており，客 $ i $ ( $ 1 \leqq i \leqq N $ ) の来店時刻は $ L_i $ ，退店時刻は $ R_i $ であった． そして今日，客のうち $ 1 $ 人が，現在 JOI 国で流行している新型の感染症 X に感染した状態で来店したことが明らかになった． 感染症 X の**感染しづらさ**は整数 $ x $ で表される． 具体的には， $ 1 \leqq i \leqq N $ について，客 $ i $ が $ 1 $ 人以上の感染者と同時に食堂内にいた時間の累計が $ x $ 以上となったタイミングで，客 $ i $ は新たに感染者となる． さて，JOI 国では厳格な感染症対策を行っているため，感染者数を正確に把握しなければならない． しかし困ったことに，誰が感染症 X に感染したかの情報は得られておらず，感染しづらさを表す整数 $ x $ も分かっていない． そこで EGOI 食堂の店長である理恵さんは， $ Q $ 個のシナリオについて，最終的に何人の客が感染するのかを求めることにした． $ j $ 番目 ( $ 1 \leqq j \leqq Q $ ) のシナリオでは，最初の感染者が客 $ P_j $ のみであり，感染症 X の感染しづらさが $ X_j $ である． 来店した客およびシナリオの情報が与えられたとき，それぞれのシナリオにおける最終的な感染者数を出力するプログラムを作成せよ． ただし，退店時刻ちょうどに感染した場合も，感染者数に含めるものとする． また，感染症 X に一度感染した客が感染者でなくなることは考えないものとする．

入力は以下の形式で与えられる． > $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $ $ Q $ $ P_1 $ $ X_1 $ $ P_2 $ $ X_2 $ $ \vdots $ $ P_Q $ $ X_Q $

$ Q $ 行出力せよ． $ j $ 行目 ( $ 1 \leqq j \leqq Q $ ) には， $ j $ 番目のシナリオにおける最終的な感染者数を出力せよ．

### 小課題 1. ( $ 2 $ 点) $ L_i = 0 $ ( $ 1 \leqq i \leqq N $ )， $ R_i = 10 $ ( $ 1 \leqq i \leqq N $ )， $ Q \leqq 5 $ ． 2. ( $ 3 $ 点) $ L_i = 0 $ ( $ 1 \leqq i \leqq N $ )， $ Q \leqq 5 $ ． 3. ( $ 6 $ 点) $ L_i = 0 $ ( $ 1 \leqq i \leqq N $ )． 4. ( $ 10 $ 点) $ N \leqq 500 $ ， $ Q \leqq 5 $ ， $ R_i \leqq 500 $ ( $ 1 \leqq i \leqq N $ )， $ X_j \leqq 500 $ ( $ 1 \leqq j \leqq Q $ )． 5. ( $ 11 $ 点) $ N \leqq 500 $ ， $ Q \leqq 5 $ ． 6. ( $ 16 $ 点) $ Q \leqq 5 $ ． 7. ( $ 13 $ 点) $ P_j = 1 $ ( $ 1 \leqq j \leqq Q $ )， $ L_1 < L_2 < \cdots < L_N $ ， $ R_1 < R_2 < \cdots < R_N $ ． 8. ( $ 14 $ 点) $ P_j = 1 $ ( $ 1 \leqq j \leqq Q $ )． 9. ( $ 15 $ 点) $ R_i - L_i $ ( $ 1 \leqq i \leqq N $ ) の最小値は， $ X_j $ ( $ 1 \leqq j \leqq Q $ ) の最大値以上である． 10. ( $ 10 $ 点) 追加の制約はない． ### Sample Explanation 1 $ 1 $ 番目のシナリオでは，最初の感染者が客 $ 1 $ ，感染症 X の感染しづらさが $ 15 $ であるため，以下のようにして感染が広がる． - 時刻 $ 10 $ に客 $ 1 $ が来店する． - 時刻 $ 20 $ に客 $ 2 $ が来店する． - 時刻 $ 35 $ に客 $ 2 $ が $ 1 $ 人以上の感染者と同時に食堂内にいた時間の累計が $ 15 $ となり，客 $ 2 $ が感染する． - 時刻 $ 40 $ に客 $ 1 $ が退店する． - 時刻 $ 45 $ に客 $ 3 $ が来店する． - 時刻 $ 60 $ に客 $ 3 $ が $ 1 $ 人以上の感染者と同時に食堂内にいた時間の累計が $ 15 $ となり，客 $ 3 $ が感染する．同時に，客 $ 3 $ が退店する． - 時刻 $ 70 $ に客 $ 4 $ が来店する． - 時刻 $ 80 $ に客 $ 2 $ が退店する． - 時刻 $ 95 $ に客 $ 4 $ が退店する．客 $ 4 $ が $ 1 $ 人以上の感染者と同時に食堂内にいたのは時刻 $ 70 $ から時刻 $ 80 $ までであり，時間の累計は $ 10 $ であるため，客 $ 4 $ は感染しない． 最終的に客 $ 1, 2, 3 $ の $ 3 $ 人が感染するため， $ 1 $ 行目には $ 3 $ を出力する． この入力例は小課題 $ 4, 5, 6, 8, 9, 10 $ の制約を満たす． ### Sample Explanation 2 $ 1 $ 番目のシナリオでは，最終的に客 $ 1, 2, 3, 4, 6, 7, 8 $ の $ 7 $ 人が感染するため， $ 1 $ 行目には $ 7 $ を出力する． $ 2 $ 番目のシナリオでは，最終的に客 $ 1 $ の $ 1 $ 人が感染するため， $ 2 $ 行目には $ 1 $ を出力する． $ 3 $ 番目のシナリオでは，最終的に客 $ 2, 3, 4, 7, 8 $ の $ 5 $ 人が感染するため， $ 3 $ 行目には $ 5 $ を出力する． この入力例は小課題 $ 2, 3, 4, 5, 6, 10 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 1, 2, 3, 5, 6, 8, 10 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 4, 5, 6, 9, 10 $ の制約を満たす． ### Sample Explanation 5 この入力例は小課題 $ 4, 5, 6, 7, 8, 9, 10 $ の制約を満たす． ### Sample Explanation 6 この入力例は小課題 $ 4, 5, 6, 8, 10 $ の制約を満たす． ### Sample Explanation 7 この入力例は小課題 $ 4, 5, 6, 9, 10 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 100\,000 $ ． - $ 0 \leqq L_i < R_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq Q \leqq 100\,000 $ ． - $ 1 \leqq P_j \leqq N $ ( $ 1 \leqq j \leqq Q $ )． - $ 1 \leqq X_j \leqq 10^9 $ ( $ 1 \leqq j \leqq Q $ )． - 入力される値はすべて整数である．