分数: 366 分
问题陈述
高桥即将购买 N 项目。项目编号从 1 to N,以及商品的价格 i is W_i 日元。
高桥有 Q 折扣券。的 j- 第一张优惠券具有对数量在 之间的每件商品进行折扣的效果 L_j 和 R_j 包括在内(即项目 L_j, L_j+1, \ldots, R_j)通过 D_j 日元各。
同一商品使用多张优惠券时,折扣金额全部累计。也就是说,如果所有优惠券的总折扣金额应用于商品 i is S_i,然后是商品的价格 i 应用所有优惠券后变为 \max(W_i - S_i,\ 0) 日元。
应用所有优惠券后,查找价格变为的商品数量 0 日元(即满足 W_i \leq S_i).
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9
- 1 \leq L_j \leq R_j \leq N
- 1 \leq D_j \leq 10^9
- 所有输入值均为整数。
输入
N Q W_1 W_2 \ldots W_N L_1 R_1 D_1 L_2 R_2 D_2 \vdots L_Q R_Q D_Q
- 第一行包含 N,项目数量,以及 Q,优惠券数量,以空格分隔。
- 第二行包含商品的初始价格 W_1, W_2, \ldots, W_N,用空格分隔。
- 以下 Q 行包含每张优惠券的信息。
- 的 (2 + j)第行包含左端点 L_j,右端点 R_j,以及折扣金额 D_j 的 j第一张优惠券,以空格分隔。
输出
在一行中打印价格变为的商品数量 使用所有优惠券后 0 日元。
样本输入 1
5 3 100 200 150 300 50 1 3 100 2 4 150 5 5 50
示例输出 1
4
示例输入 2
7 4 500 300 200 400 100 600 250 1 4 200 3 5 150 2 6 100 4 7 300
示例输出 2
5
示例输入 3
10 6 1000000000 500 200 800 1200 300 450 100 900 600 1 5 600 3 7 250 1 3 400 6 10 400 2 8 200 5 9 500
示例输出 3
8