分数: 400 分
问题陈述
有 N 路灯沿着某条街道排成一排。
初始亮度 i第路灯是 A_i。亮度降低 D_i 每天,但不低于 0。也就是说,亮度 i第-路灯后 t 天是
C_i(t) = \max(0,\ A_i - D_i \times t)
亮度为 时间 K 或更少 t 天后被称为“黑暗的路灯”。
的 暗子区间数 之后 t 天数定义如下:它是整数对的数量 (l, r) 满意 1 \leq l \leq r \leq N 这样所有的路灯都来自 l-第 r- 之后街灯变暗 t 天。
在这里, (l, r) 不需要是最大连续间隔;所有满足条件的对都被计数。例如,如果 m 连续路灯全黑,对数 可以从中选择的 (l, r) 是 \frac{m(m+1)}{2},所有这些都被计算在内。 给出了
Q 查询。对于 j第一个查询,查找之后的暗子区间数 T_j 天。
约束
- 1 \leq N, Q
- N + Q \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq T_j \leq 10^9 (1 \leq j \leq Q)
- 所有输入均为整数
- 每个查询的答案都包含在 64 位有符号整数中
输入
N Q K A_1 D_1 A_2 D_2 \vdots A_N D_N T_1 T_2 \vdots T_Q
- 第一行包含 N 代表路灯数量, Q 代表查询数量,以及 K 表示用于确定黑暗的亮度阈值,以空格分隔。
- 以下 N 行提供有关每个路灯的信息。
- 的 (1 + i)第行包含初始亮度 A_i 的 i第路灯和亮度每天下降 D_i,用空格分隔。
- 以下 Q 行给出查询。
- 的 (1 + N + j)- 第行包含天数 T_j 为 j- 第一个查询。
输出
输出 Q 行。
关于 j第行,输出之后的暗子区间数 T_j 天。
示例输入 1
5 4 10 15 2 8 0 30 5 10 1 25 3 0 2 4 10
示例输出 1
2 2 10 15
示例输入 2
4 5 5 6 0 5 0 20 10 1 0 0 1 2 3 10
示例输出 2
2 2 6 6 6
示例输入 3
10 8 20 50 5 18 0 100 10 21 1 0 0 35 3 80 20 20 0 60 4 25 2 0 1 2 3 5 7 10 20
示例输出 3
3 5 5 8 17 19 55 55
示例输入 4
25 12 100 150 10 90 0 300 20 101 1 500 50 0 0 250 5 120 30 100 0 1000 100 80 2 450 25 600 0 110 3 700 70 95 1 130 15 100 5 1000000000 100000000 400 40 200 0 105 2 10000 500 99 0 160 8 0 1 2 3 5 7 10 15 20 50 100 1000000000
示例输出 4
7 10 14 15 18 18 63 68 74 116 116 116
示例输入 5
1 1 0 1000000000 1000000000 1000000000
示例输出 5
1