← 返回题目列表

AtCoder · awc0069_e

E. 图书馆库存检查

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

分数: 466 分

问题陈述

高桥在一家大型图书馆担任图书管理员。这个图书馆有 N 书架排列成一排,编号 1, 2, \ldots, N 从左到右。

书架 i (1 \leq i \leq N) 包含 A_i 书籍。这些书目前正在修复中,书架上的所有书 i 将于当天完成修复 D_i。修复完成后,这些书籍就可供借阅。也就是书架上的书 i 从当天起即可借出 D_i 以后(包括当天 D_i)。当书架上的书 i 被借出,用户支付费用 V_i 图书馆每本书日元。

高桥正在考虑 Q 贷款计划。每个计划都是独立于其他计划的;一个计划中借出的书籍不会影响其他计划。

计划中 j (1 \leq j \leq Q),连续的书架间隔 [L_j, R_j] (1 \leq L_j \leq R_j \leq N)和日期 已指定 T_j 。在这个计划中,区间的书架之中 [L_j, R_j],白天恢复完成的 T_j (即书架 i 满意 D_i \leq T_j)将拥有所有 A_i 书籍借出。书架上未完成修复的图书将不予外借。

当所有 A_i 书架上的书 i 被借出,赚取的费用为 A_i \times V_i 日元。

对于每个计划,确定从贷款中赚取的总费用。即计划中赚取的总费用 j 是:

\sum_{\substack{L_j \leq i \leq R_j \\ D_i \leq T_j}} A_i \times V_i

约束

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^4
  • 1 \leq D_i \leq 10^5
  • 1 \leq V_i \leq 10^4
  • 1 \leq L_j \leq R_j \leq N
  • 1 \leq T_j \leq 10^5
  • 所有输入均为整数
  • 对于每个计划,答案最多为 2 \times 10^{13}

输入

N Q
A_1 D_1 V_1
A_2 D_2 V_2
\vdots
A_N D_N V_N
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q
  • 第一行包含书架数量 N 及贷款计划数量 Q,用空格分隔。
  • 如下 N 行, i-第行包含书籍数量 A_i 在书架上 i,恢复完成日 D_i,以及每本书的费用 V_i,以空格分隔。
  • 如下 Q 行, j第行包含左端点 L_j,右端点 R_j和日期 T_j 计划 j,以空格分隔。

输出

输出 Q 行。上 j第行,输出计划中赚取的总费用 j 作为整数。


示例输入 1

5 4
2 1 100
3 3 50
1 2 200
5 5 10
4 3 25
1 3 2
2 5 3
1 5 5
4 4 4

示例输出 1

400
450
700
0

示例输入 2

3 5
1 10 5
2 20 7
3 30 11
1 3 9
1 1 10
2 3 25
3 3 30
1 3 100

示例输出 2

0
5
14
33
52

示例输入 3

10 8
5 4 120
2 1 300
7 6 80
1 3 1000
4 5 250
6 2 90
3 8 400
8 7 60
10 4 30
9 9 110
1 10 4
3 7 5
2 9 2
5 10 8
1 1 3
4 6 10
7 10 6
2 5 1

示例输出 3

3040
2540
1140
3520
0
2540
300
600

示例输入 4

30 20
10 15 100
25 3 40
7 22 500
100 1 20
13 18 70
6 9 1000
80 30 15
2 5 600
45 12 90
11 7 250
9 40 800
30 25 35
16 2 120
5 17 900
60 11 45
3 35 700
22 6 110
14 28 330
50 19 55
8 4 1000
19 23 75
4 14 650
70 8 25
12 31 400
33 10 60
1 100000 10000
90 13 30
18 21 200
27 16 85
40 24 95
1 30 10
1 30 100000
5 20 18
10 15 7
16 30 25
1 8 5
21 26 99999
26 26 100000
3 27 12
8 23 30
12 29 20
2 2 2
4 4 1
14 18 35
19 30 23
6 17 11
24 30 31
1 1 14
7 13 40
28 30 15

示例输出 4

29020
95820
34450
4670
33320
4200
12555
10000
34770
41735
33615
0
2000
16340
27100
16990
19175
0
19370
0

示例输入 5

1 1
10000 100000 10000
1 1 99999

示例输出 5

0