宝石商(Jeweler)

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

The 25^th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)

• 1 ≦N ≦300 000.
• 1 ≦Li < Ri ≦1 000 000 (1 ≦i ≦N).
• 1 ≦Ci ≦109 (1 ≦i ≦N).
• 1 ≦M ≦300 000.
• 1 ≦S j ≦T j ≦1 000 000 (1 ≦j ≦M).
• 入力される値はすべて整数である.

1. (12 点) N ≦1 000,M ≦1 000.
2. (17 点) S j = T j (1 ≦j ≦M).
3. (21 点) S j = 1 (1 ≦j ≦M).
4. (23 点) S j ≦S j+1,T j ≦T j+1 (1 ≦j < M).
5. (27 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.
N
L1 R1 C1
L2 R2 C2
...
LN RN CN
M
S 1 T1
S 2 T2
...
S M TM

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

The 25^th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)

생성자가 기록되지 않았습니다.

출처 JOI 2026 Semifinal