分数: 366 分
问题陈述
高桥负责管理他花园里的花坛。花坛有 N 花连续种植,编号花 1, 花 2, \ldots, 花 N 从左到右。浇水前,花的高度 i is H_i.
高桥给花浇水 M 天。当天 j (j = 1, 2, \ldots, M),他浇花 L_j, L_j + 1, \ldots, R_j。每朵浇水的花的高度都会增加 W_j 每朵花.
花的高度 i 毕竟 M 浇水完成的天数称为最终花高 i。花 如果 i 的最终高度至少达到目标高度,则被视为“充分生长” T_i.
找出充分生长的花朵的数量。
约束
- 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 T_i \leq 10^{18} (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 H_1 H_2 \ldots H_N T_1 T_2 \ldots T_N L_1 R_1 W_1 L_2 R_2 W_2 \vdots L_M R_M W_M
- 第一行包含一个整数 N 代表鲜花的数量和一个整数 M 代表浇水天数,用空格分隔。
- 第二行包含整数 H_1, H_2, \ldots, H_N 代表浇水前花朵的高度,以空格分隔。
- 第三行包含整数 T_1, T_2, \ldots, T_N 代表花朵的目标高度,以空格分隔。
- 的 树的 j- 以下各项 M 行包含左端点 L_j,右端点 当天浇水的间隔 R_j 一天浇水的间隔时间 j,以及每朵花的高度增加 W_j 浇水,用空格分隔。
输出
在一行中输出充分生长的花朵的数量。
示例输入 1
5 3 10 20 30 40 50 25 35 50 40 80 1 3 5 2 4 10 1 5 3
示例输出 1
2
示例输入 2
8 4 1 1 1 1 1 1 1 1 10 15 20 25 20 15 10 5 1 8 5 2 7 5 3 6 5 4 5 5
示例输出 2
4
示例输入 3
10 5 1000000000 500000000 1 999999999 100 200 300 400 500 600 1000000000000000000 1000000000 100 2000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1 10 1000000000 1 5 1000000000 3 8 1000000000 1 10 1000000000 5 10 1000000000
示例输出 3
9