← 返回题目列表

AtCoder · awc0091_d

D. 路灯的黑暗间隔

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

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