← 返回题目列表

AtCoder · awc0048_c

C. 路灯和暴风雪

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

分数: 366 分

问题陈述

高桥是一座城市的管理者。沿着主街, N 路灯排成一排,从左到右编号为路灯 1,路灯 2, \ldots,路灯 N。路灯初始耐久性 i (1 \leq i \leq N)是 H_i。路灯的耐用性变得 0 或更少被认为已经倒塌。

这个冬天, M 暴风雪即将来临。的 j-th 暴风雪 (1 \leq j \leq M) 降低路灯范围内所有路灯的耐用性 L_j 到路灯 R_j by D_j.

每个路灯的最终耐久度是其初始耐久度减去所有暴风雪造成的总耐久度。也就是说,即使路灯的耐用性变成 0 或中途,它不能免受随后暴风雪造成的下降的影响。

所有暴风雪过去后,确定最终耐久度为的路灯数量 1 或更多(即尚未折叠)。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
  • 所有输入值均为整数。

输入

N M
H_1 H_2 \ldots H_N
L_1 R_1 D_1
L_2 R_2 D_2
\vdots
L_M R_M D_M
  • 第一行包含路灯数量 N 和暴风雪的数量 M,用空格分隔。
  • 第二行包含初始耐久性 每个路灯的 H_1, H_2, \ldots, H_N ,以空格分隔。
  • 以下 M 行提供有关每次暴风雪的信息。的 j第行包含左端点 L_j,右端点 R_j 的影响范围 j第-次暴风雪,耐久度下降 D_j,用空格分隔。

输出

在一行中打印最终耐用度为的路灯数量 1 或所有暴风雪过去后更多。


示例输入 1

5 2
10 5 8 3 7
2 4 3
1 3 4

示例输出 1

3

示例输入 2

3 2
3 2 1
1 3 2
1 1 1

示例输出 2

0

示例输入 3

10 5
100 50 30 80 60 40 90 20 70 10
1 5 20
3 8 15
6 10 25
1 10 10
2 4 30

示例输出 3

5

示例输入 4

15 6
1000000000 500 300 800 600 400 900 200 700 100 550 350 750 450 1000000000
1 15 100
1 8 200
5 12 150
3 10 50
7 15 100
1 15 50

示例输出 4

10

示例输入 5

1 1
1
1 1 1

示例输出 5

0