分数: 366 分
问题陈述
高桥作为学校园艺委员会的一部分负责管理花坛。
花坛有 N 花连续种植,编号花 1, 花 2,……,花 N 从左到右。每朵花 i 具有耐湿性 S_i 由其物种决定。
高桥将表演 M 浇水作业。在进行任何浇水操作之前,没有花朵接受过任何水。在 j第次操作,他给了一定量的水 W_j 从花到每一朵花 L_j 要花 R_j.
所有浇水操作完成后,如果花收到的水总量 i (即给予花的水量的总和 i 在所有浇水操作中)严格大于其耐湿性 S_i,然后花 i 遭受“根腐病”。如果总量小于或等于耐湿量,则不会发生根腐病。
找出遭受根腐病的花朵数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq S_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 W_j \leq 10^9 (1 \leq j \leq M)
- 所有输入均为整数
输入
N M S_1 S_2 \ldots S_N L_1 R_1 W_1 L_2 R_2 W_2 \vdots L_M R_M W_M
- 第一行包含 N,鲜花数量,以及 M,浇水操作的次数,以空格分隔。
- 第二行包含水分容差 每朵花的 S_1, S_2, \ldots, S_N ,用空格分隔。
- 如下 M 行, j第行包含左端点 L_j,右端点 R_j 花卉浇水范围 j第次操作,以及水量 W_j 赋予每朵花,以空格分隔。
输出
在一行上打印所有浇水操作完成后发生根部腐烂的花朵的数量。
样本输入 1
5 2 10 5 8 12 3 1 3 4 2 5 6
示例输出 1
3
示例输入 2
7 4 15 20 10 25 30 5 18 1 4 8 3 6 12 2 5 5 4 7 10
示例输出 2
3
示例输入 3
10 6 100 50 80 120 60 90 40 110 70 55 1 5 30 3 8 25 6 10 35 2 4 40 5 7 20 1 10 10
示例输出 3
4