D - Dark Intervals of Street Lights Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

ある通りに N 本の街灯が一列に並んでいます。

i 番目の街灯のはじめの明るさは A_i です。明るさは 1 日あたり D_i ずつ低下しますが、0 未満にはなりません。すなわち、t 日後の i 番目の街灯の明るさは

C_i(t) = \max(0,\ A_i - D_i \times t)

です。

t 日後の時点で明るさが K 以下である街灯を「暗い街灯」と呼びます。

t 日後における暗い部分区間の個数を、次のように定義します。1 \leq l \leq r \leq N を満たす整数の組 (l, r) であって、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
  • 1 行目には、街灯の本数を表す N、問い合わせの数を表す Q、暗いと判定する明るさの閾値 K が、スペース区切りで与えられる。
  • 続く N 行では、各街灯の情報が与えられる。
  • 1 + i 行目には、i 番目の街灯のはじめの明るさ A_i と、1 日あたりに低下する明るさ D_i が、スペース区切りで与えられる。
  • 続く Q 行では、問い合わせが与えられる。
  • 1 + N + j 行目には、j 番目の問い合わせの日数 T_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

Score : 400 pts

Problem Statement

There are N street lights lined up in a row along a certain street.

The initial brightness of the i-th street light is A_i. The brightness decreases by D_i per day, but does not go below 0. That is, the brightness of the i-th street light after t days is

C_i(t) = \max(0,\ A_i - D_i \times t)

A street light whose brightness is K or less at time t days later is called a "dark street light."

The number of dark subintervals after t days is defined as follows: it is the number of pairs of integers (l, r) satisfying 1 \leq l \leq r \leq N such that all street lights from the l-th to the r-th are dark street lights after t days.

Here, (l, r) does not need to be a maximal contiguous interval; all pairs satisfying the condition are counted. For example, if m consecutive street lights are all dark, the number of pairs (l, r) that can be chosen from them is \frac{m(m+1)}{2}, and all of them are counted.

Q queries are given. For the j-th query, find the number of dark subintervals after T_j days.

Constraints

  • 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)
  • All inputs are integers
  • The answer to each query fits in a 64-bit signed integer

Input

N Q K
A_1 D_1
A_2 D_2
\vdots
A_N D_N
T_1
T_2
\vdots
T_Q
  • The first line contains N representing the number of street lights, Q representing the number of queries, and K representing the brightness threshold for determining darkness, separated by spaces.
  • The following N lines give information about each street light.
  • The (1 + i)-th line contains the initial brightness A_i of the i-th street light and the brightness decrease per day D_i, separated by a space.
  • The following Q lines give the queries.
  • The (1 + N + j)-th line contains the number of days T_j for the j-th query.

Output

Output Q lines.

On the j-th line, output the number of dark subintervals after T_j days.

Sample Input 1

5 4 10
15 2
8 0
30 5
10 1
25 3
0
2
4
10

Sample Output 1

2
2
10
15

Sample Input 2

4 5 5
6 0
5 0
20 10
1 0
0
1
2
3
10

Sample Output 2

2
2
6
6
6

Sample Input 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

Sample Output 3

3
5
5
8
17
19
55
55

Sample Input 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

Sample Output 4

7
10
14
15
18
18
63
68
74
116
116
116

Sample Input 5

1 1 0
1000000000 1000000000
1000000000

Sample Output 5

1