← 返回题目列表

AtCoder · awc0054_c

C. 给花坛浇水

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

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