C - 川を行くボート 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君はまっすぐな川でボートに乗っています。川は東西方向に流れており、東を正の方向とする数直線上で高橋君の位置を表します。

時刻 0 において、高橋君は座標 0 の位置にいます。

川の流れは以下のように変化します。流れが変化する時刻 T_1, T_2, \ldots, T_N（T_1 < T_2 < \cdots < T_N）と、それぞれの変化後の川の流れの速度 W_1, W_2, \ldots, W_N が与えられます。W_i > 0 は東向き、W_i < 0 は西向きの流れを意味します。すべての i について W_i \neq 0 が保証されます。

各時間帯における川の流れの速度は次の通りです：

  • 時刻 0 以上 T_1 未満の間：川の流れはありません（速度 0）。
  • i = 1, 2, \ldots, N-1 について、時刻 T_i 以上 T_{i+1} 未満の間：川の流れの速度は W_i です。
  • 時刻 T_N 以降：川の流れの速度は W_N です。

高橋君のボートの漕ぎ方には次のルールがあります：

  • 川の流れがないとき、高橋君はボートを漕がず、その場に留まります。
  • 川の流れがあるとき、高橋君は常に流れと同じ方向に、水面に対して速さ V でボートを漕ぎます。すなわち、川の流れの速度を W（W \neq 0）とすると、高橋君は流れの方向に速さ |W| + V で移動します。東を正とした地面に対する速度で表すと、流れが東向き（W > 0）のとき W + V、流れが西向き（W < 0）のとき W - V です。

高橋君の座標は時間の経過とともに連続的に変化します（流れの速度が切り替わる瞬間に座標が飛ぶことはありません）。

Q 個の質問が与えられます。j 番目の質問では、時刻 X_j における高橋君の座標を求めてください。

なお、制約の範囲において、各質問の答えは必ず整数であり、符号付き 64 bit 整数に収まります。

制約

  • 1 \leq N
  • 1 \leq Q \leq 10^5
  • N + Q \leq 2 \times 10^5
  • 1 \leq V \leq 10^9
  • 1 \leq T_1 < T_2 < \cdots < T_N \leq 10^9
  • -10^9 \leq W_i \leq 10^9
  • W_i \neq 0 （1 \leq i \leq N）
  • 0 \leq X_j \leq 10^9 （1 \leq j \leq Q）
  • N, Q, T_i, W_i, V, X_j はすべて整数

入力

N V Q
T_1 W_1
T_2 W_2
\vdots
T_N W_N
X_1
X_2
\vdots
X_Q
  • 1 行目には、川の流れの変化の回数を表す整数 N、高橋君が水面に対してボートを漕ぐ速さを表す整数 V、質問の数を表す整数 Q が、空白区切りで与えられる。
  • 2 行目から N + 1 行目では、川の流れの変化の情報が N 行で与えられる。
  • 1 + i 行目（1 \leq i \leq N）では、i 回目の変化が起こる時刻 T_i と、その時刻以降の川の流れの速度 W_i が、空白区切りで与えられる。
  • N + 2 行目から N + 1 + Q 行目では、質問の時刻が Q 行で与えられる。
  • N + 1 + j 行目（1 \leq j \leq Q）では、j 番目の質問の時刻 X_j が与えられる。

出力

Q 行出力せよ。j 行目には、時刻 X_j における高橋君の座標を整数で出力せよ。

入力例 1

3 2 6
3 1
7 -2
10 3
0
3
5
7
9
12

出力例 1

0
0
6
12
4
10

入力例 2

2 5 5
2 -3
6 4
1
2
4
6
8

出力例 2

0
0
-16
-32
-14

入力例 3

7 4 10
5 2
12 -6
20 1
35 -3
50 8
65 -1
80 5
0
5
10
12
25
35
49
50
70
100

出力例 3

0
0
30
42
-13
37
-61
-68
87
217

入力例 4

18 12345 22
1 1000000000
10 -999999999
100 500
1000 -400
10000 30000
50000 -20000
100000 1
200000 -1
500000 700000
1000000 -800000
5000000 123456789
10000000 -987654321
50000000 42
100000000 -42
250000000 31415926
500000000 -27182818
750000000 999
900000000 -1000
0
1
9
10
55
999
1000
12345
50000
150000
499999
500000
999999
1000000
7500000
50000000
123456789
250000000
600000000
900000000
950000000
1000000000

出力例 4

0
0
8000098760
9000111105
-36000444375
-80989452200
-80989439355
-81004845330
-79410344355
-80410294355
-83496782009
-83496794355
272674993300
272675705645
305696130705645
-38892297674294355
-38891968883539698
-38893536374294355
-33755984924294355
-37833257774294355
-37833925024294355
-37834592274294355

入力例 5

1 1000000000 1
1000000000 -1000000000
1000000000

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is riding a boat on a straight river. The river flows in the east-west direction, and Takahashi's position is represented on a number line where east is the positive direction.

At time 0, Takahashi is at coordinate 0.

The flow of the river changes over time. You are given the times T_1, T_2, \ldots, T_N (T_1 < T_2 < \cdots < T_N) when the flow changes, and the velocity of the river's flow after each change, W_1, W_2, \ldots, W_N. W_i > 0 represents an eastward flow, and W_i < 0 represents a westward flow. It is guaranteed that W_i \neq 0 for all i.

The velocity of the river's flow during each time interval is as follows:

  • From time 0 to less than T_1: There is no river flow (velocity 0).
  • For i = 1, 2, \ldots, N-1, from time T_i to less than T_{i+1}: The velocity of the river flow is W_i.
  • From time T_N onwards: The velocity of the river flow is W_N.

Takahashi rows his boat according to the following rules:

  • When there is no river flow, Takahashi does not row his boat and stays in place.
  • When there is river flow, Takahashi always rows his boat in the same direction as the flow at a speed of V relative to the water surface. That is, if the river flow velocity is W (W \neq 0), Takahashi moves in the direction of the flow at a speed of |W| + V. Expressed as velocity relative to the ground (where east is positive), this is W + V when the flow is eastward (W > 0), and W - V when the flow is westward (W < 0).

Takahashi's coordinate changes continuously over time (his coordinate does not jump at the exact moment the flow velocity changes).

You are given Q queries. In the j-th query, find Takahashi's coordinate at time X_j.

Under the constraints, the answer to each query is guaranteed to be an integer and fit within a signed 64-bit integer.

Constraints

  • 1 \leq N
  • 1 \leq Q \leq 10^5
  • N + Q \leq 2 \times 10^5
  • 1 \leq V \leq 10^9
  • 1 \leq T_1 < T_2 < \cdots < T_N \leq 10^9
  • -10^9 \leq W_i \leq 10^9
  • W_i \neq 0 (1 \leq i \leq N)
  • 0 \leq X_j \leq 10^9 (1 \leq j \leq Q)
  • N, Q, T_i, W_i, V, X_j are all integers.

Input

N V Q
T_1 W_1
T_2 W_2
\vdots
T_N W_N
X_1
X_2
\vdots
X_Q
  • The first line contains three space-separated integers: N, the number of times the river flow changes; V, Takahashi's rowing speed relative to the water surface; and Q, the number of queries.
  • The next N lines, from the 2nd line to the (N + 1)-th line, provide information about the changes in the river flow.
  • The (1 + i)-th line (1 \leq i \leq N) contains two space-separated integers: T_i, the time of the i-th change, and W_i, the velocity of the river flow from that time onwards.
  • The next Q lines, from the (N + 2)-th line to the (N + 1 + Q)-th line, provide the query times.
  • The (N + 1 + j)-th line (1 \leq j \leq Q) contains X_j, the time for the j-th query.

Output

Print Q lines. The j-th line should contain Takahashi's coordinate at time X_j as an integer.

Sample Input 1

3 2 6
3 1
7 -2
10 3
0
3
5
7
9
12

Sample Output 1

0
0
6
12
4
10

Sample Input 2

2 5 5
2 -3
6 4
1
2
4
6
8

Sample Output 2

0
0
-16
-32
-14

Sample Input 3

7 4 10
5 2
12 -6
20 1
35 -3
50 8
65 -1
80 5
0
5
10
12
25
35
49
50
70
100

Sample Output 3

0
0
30
42
-13
37
-61
-68
87
217

Sample Input 4

18 12345 22
1 1000000000
10 -999999999
100 500
1000 -400
10000 30000
50000 -20000
100000 1
200000 -1
500000 700000
1000000 -800000
5000000 123456789
10000000 -987654321
50000000 42
100000000 -42
250000000 31415926
500000000 -27182818
750000000 999
900000000 -1000
0
1
9
10
55
999
1000
12345
50000
150000
499999
500000
999999
1000000
7500000
50000000
123456789
250000000
600000000
900000000
950000000
1000000000

Sample Output 4

0
0
8000098760
9000111105
-36000444375
-80989452200
-80989439355
-81004845330
-79410344355
-80410294355
-83496782009
-83496794355
272674993300
272675705645
305696130705645
-38892297674294355
-38891968883539698
-38893536374294355
-33755984924294355
-37833257774294355
-37833925024294355
-37834592274294355

Sample Input 5

1 1000000000 1
1000000000 -1000000000
1000000000

Sample Output 5

0