P15452 [JOI 2026 SemiFinal] 宝石商 / Jeweler

JOI 君は宝石店を経営している．宝石店には宝石を買おうとしている客が $N$ 人おり，これらの客には $1$ から $N$ までの番号が付けられている．客 $i$ ($1 \le i \le N$) は時刻 $L_i$ から時刻 $R_i$ までの間の任意の時刻に店を訪れることができ，宝石を $C_i$ 個購入しようとしている． JOI 君は忙しいため，常に店を開けておくことができない．そこで，店を開ける時間について $M$ 個の案を考えた．案には $1$ から $M$ までの番号が付けられており，案 $j$ ($1 \le j \le M$) は，時刻 $S_j - 0.1$ から時刻 $T_j + 0.1$ までの間店を開けるというものである．それぞれの案について，客 $i$ ($1 \le i \le N$) は，自分が訪れることができる時間帯に店が開いている時刻があれば，店を訪れ宝石を $C_i$ 個購入する．逆にそうでない場合，客 $i$ は店を訪れず，宝石を購入しない．ただし，JOI 君の店には十分な数の宝石があり，宝石が売り切れることはないものとする． JOI 君の店の客の情報と店を開けておく時間の案が与えられたとき，それぞれの案について，宝石が合計でいくつ売れるかを求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． $N$ $L_1\ R_1\ C_1$ $L_2\ R_2\ C_2$ $\vdots$ $L_N\ R_N\ C_N$ $M$ $S_1\ T_1$ $S_2\ T_2$ $\vdots$ $S_M\ T_M$

標準出力に $M$ 行出力せよ．$j$ 行目 ($1 \le j \le M$) には，案 $j$ において宝石が合計でいくつ売れるかを出力せよ．

### Sample Explanation 1 案 1 では，時刻 $3.9$ から時刻 $6.1$ まで店を開ける．客 1 は時刻 $4$ に，客 2 は時刻 $5$ に，客 3 は時刻 $6$ に店で宝石を買うことができ，宝石は合計で $10 + 20 + 30 = 60$ 個売れる． 案 2 では，時刻 $0.9$ から時刻 $2.1$ まで店を開ける．どの客も店が開いている時刻に訪れることができないため，宝石は合計で $0$ 個売れる． 案 3 では，時刻 $5.9$ から時刻 $8.1$ まで店を開ける．客 2，客 3 ともに時刻 $7$ に店で宝石を買うことができ，宝石は合計で $20 + 30 = 50$ 個売れる． この入力例は小課題 1, 5 の制約を満たす． ### Sample Explanation 2 案 1 では，客 1 と客 3 が店で宝石を買うことができ，宝石は合計で $1 + 4 = 5$ 個売れる． 案 2 では，客 1，客 2，客 3 が店で宝石を買うことができ，宝石は合計で $1 + 2 + 4 = 7$ 個売れる． 案 3 では，すべての客が店で宝石を買うことができ，宝石は合計で $1 + 2 + 4 + 8 = 15$ 個売れる． この入力例は小課題 1, 3, 4, 5 の制約を満たす． ### 制約 - $1 \le N \le 300\,000$． - $1 \le L_i < R_i \le 1\,000\,000$ ($1 \le i \le N$)． - $1 \le C_i \le 10^9$ ($1 \le i \le N$)． - $1 \le M \le 300\,000$． - $1 \le S_j \le T_j \le 1\,000\,000$ ($1 \le j \le M$)． - 入力される値はすべて整数である． ### 小課題 1. $(12$ 点$) N \le 1000,\ M \le 1000$． 2. $(17$ 点$) S_j = T_j$ ($1 \le j \le M$)． 3. $(21$ 点$) S_j = 1$ ($1 \le j \le M$)． 4. $(23$ 点$) S_j \le S_{j+1},\ T_j \le T_{j+1}$ ($1 \le j < M$)． 5. $(27$ 点$) $追加の制約はない．