← 返回题目列表

AtCoder · awc0066_c

C. 折扣券

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

分数: 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