← 返回题目列表

AtCoder · joi2026_semifinal_b

B. 珠宝商

中文机器翻译题面 查看原题

配点: 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).
  • 所有输入值都是整数。

小課題

  1. (12 点) N \leqq 1\,000,M \leqq 1\,000.
  2. (17 点) S_j = T_j (1 \leqq j \leqq M).
  3. (21 点) S_j = 1 (1 \leqq j \leqq M).
  4. (23 点) S_j \leqq S_{j+1},T_j \leqq T_{j+1} (1 \leqq j < M).
  5. (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 。