P15452 [JOI 2026 SemiFinal] Jeweler

JOI runs a jewelry shop. There are $N$ customers who want to buy jewels, numbered from $1$ to $N$. Customer $i$ ($1 \le i \le N$) can visit the shop at any time between time $L_i$ and time $R_i$, and plans to buy $C_i$ jewels. JOI is very busy and cannot keep the shop open all the time. Therefore, he considers $M$ possible opening-time plans. The plans are numbered from $1$ to $M$, and plan $j$ ($1 \le j \le M$) means the shop is open from time $S_j - 0.1$ to time $T_j + 0.1$. For each plan, customer $i$ ($1 \le i \le N$) will visit the shop and buy $C_i$ jewels if there exists a time when the shop is open within the time interval in which they can visit. Otherwise, if no such time exists, customer $i$ will not visit and will not buy any jewels. However, JOI’s shop has enough jewels, so it will never run out. Given the customer information and each opening-time plan, write a program to compute, for each plan, the total number of jewels that can be sold.

The input is given from standard input in the following format: $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$

Output $M$ lines to standard output. On the $j$-th line ($1 \le j \le M$), output the total number of jewels that can be sold under plan $j$.

#### Sample Explanation 1 In plan 1, the shop is open from time $3.9$ to time $6.1$. Customer 1 can come at time $4$, customer 2 can come at time $5$, and customer 3 can come at time $6$ to buy jewels. In total, $10 + 20 + 30 = 60$ jewels are sold. In plan 2, the shop is open from time $0.9$ to time $2.1$. No customer can visit during the opening time, so a total of $0$ jewels are sold. In plan 3, the shop is open from time $5.9$ to time $8.1$. Customers 2 and 3 can both come at time $7$ to buy jewels. In total, $20 + 30 = 50$ jewels are sold. This sample input satisfies the constraints for subtasks 1 and 5. #### Sample Explanation 2 In plan 1, customers 1 and 3 can visit the shop to buy jewels. In total, $1 + 4 = 5$ jewels are sold. In plan 2, customers 1, 2, and 3 can visit the shop to buy jewels. In total, $1 + 2 + 4 = 7$ jewels are sold. In plan 3, all customers can visit the shop to buy jewels. In total, $1 + 2 + 4 + 8 = 15$ jewels are sold. This sample input satisfies the constraints for subtasks 1, 3, 4, and 5. ### Constraints - $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$) - All input values are integers. ### Subtasks 1. (12 points) $N \le 1000,\ M \le 1000$ 2. (17 points) $S_j = T_j$ ($1 \le j \le M$) 3. (21 points) $S_j = 1$ ($1 \le j \le M$) 4. (23 points) $S_j \le S_{j+1},\ T_j \le T_{j+1}$ ($1 \le j < M$) 5. (27 points) No additional constraints. Translated by DeepSeek. Translated by ChatGPT 5