配点: 100 点
問題文
JOI 你经营一家珠宝店。 珠宝店里,有顾客想要购买珠宝。 N 有人,这些客户有 它们的编号最大为 1 我决定将所有值添加到 N 。 顾客 i (1 \leqq i \leqq N) 是时间 L_i 到时间 您可以在 R_i 之间的任何时间访问商店并领取您的珠宝。 我正在尝试购买 C_i 。
JOI 你太忙了,没时间让商店一直营业。 那么,关于店铺的营业时间, 我想到了 M 的想法。 计划中 草稿编号最大为 1 我决定将所有值添加到 M 。 j (1 \leqq j \leqq M) 是时间 商店将继续营业至 S_j - 0.1 到时间 您可以在 T_j + 0.1 。 对于每个提案, i (1 \leqq i \leqq 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 \leqq j \leqq M) 有草稿 打印 j 中售出的珠宝总数。
制約
- 1 \leqq N \leqq 300\,000.
- 1 \leqq L_i < R_i \leqq 1\,000\,000 (1 \leqq i \leqq N).
- 1 \leqq C_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq M \leqq 300\,000.
- 1 \leqq S_j \leqq T_j \leqq 1\,000\,000 (1 \leqq j \leqq M).
- 所有输入值都是整数。
小課題
- (12 点) N \leqq 1\,000,M \leqq 1\,000.
- (17 点) S_j = T_j (1 \leqq j \leqq M).
- (21 点) S_j = 1 (1 \leqq j \leqq M).
- (23 点) S_j \leqq S_{j+1},T_j \leqq T_{j+1} (1 \leqq j < M).
- (27 点)没有额外的限制。
入力例 1
3 3 4 10 5 8 20 6 10 30 3 4 6 1 2 6 8
出力例 1
60 0 50
案 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 。
入力例 2
4 10 90 1 40 60 2 10 20 4 80 90 8 3 1 15 1 60 1 100
出力例 2
5 7 15
案 1 然后,客户 1 和客户 3 可以在商店购买珠宝,珠宝总量为 1 + 4 = 5 可以出售。 提案 在 2 然后,客户 1,客 2,客 3 可以在商店购买珠宝,珠宝总量为 1 + 2 + 4 = 7 可以出售。 提案 在 3 中,所有顾客都可以在商店购买珠宝,珠宝总量为 1 + 2 + 4 + 8 = 15 可以单位出售。 商店将营业至
此输入示例是一个小作业。 1,3,4,5 。
入力例 3
10 55 882 861052753 104 734 331227764 492 694 240198464 481 506 377367203 131 185 327968773 124 129 970226535 92 125 133053911 356 442 758055457 21 759 730522637 259 481 948997757 9 50 287 510 735 158 431 113 768 328 894 783 881 163 692 42 862 43 752
出力例 3
4303050130 2163001618 3957825141 5678671254 4247422035 861052753 4575390808 5678671254 5678671254
此输入示例是一个小作业。 1,5 。