← 返回题目列表

AtCoder · awc0111_c

C. 给花坛浇水

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

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