D - パレードの撮影 解説 /

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

配点 : 400 点

問題文

高橋君は、直線の道路上を移動する N 台の山車（だし）のパレードを撮影しようとしています。

撮影日は 0 日目から D 日目までの整数日の中から 1 日選びます。高橋君は、すべての山車が収まるようにカメラのフレーム幅をできるだけ小さくしたいと考えています。

d 日目における山車 i の中心座標は X_i + V_i \cdot d です。ここで X_i は 0 日目の中心座標、V_i は 1 日あたりの移動速度（負なら座標が減る方向に移動）です。また、山車 i は中心から左右にそれぞれ L_i の半幅を持つため、道路上で区間

[X_i + V_i \cdot d - L_i, \ X_i + V_i \cdot d + L_i]

を占有します。

d 日目にすべての山車を収めるために必要なフレーム幅は

F(d) = \max_{1 \le i \le N}(X_i + V_i \cdot d + L_i) - \min_{1 \le i \le N}(X_i + V_i \cdot d - L_i)

です。

ところが、青木君からパレードの運行計画について Q 回の修正指示が届きました。j 回目の修正では、山車 P_j の初期座標・移動速度・半幅がそれぞれ A_j, B_j, C_j に変更されます。

バージョン 0 を初期データ、バージョン j（1 \le j \le Q）をバージョン j-1 に j 回目の修正を反映したデータとします。バージョン t における山車 i の初期座標、移動速度、半幅をそれぞれ X_i^{(t)}, V_i^{(t)}, L_i^{(t)} と表すとき、バージョン t における日 d のフレーム幅は

F_t(d) = \max_{1 \le i \le N}(X_i^{(t)} + V_i^{(t)} \cdot d + L_i^{(t)}) - \min_{1 \le i \le N}(X_i^{(t)} + V_i^{(t)} \cdot d - L_i^{(t)})

です。

各バージョン t（0 \le t \le Q）について、撮影日を最適に選んだときのフレーム幅の最小値

G_t = \min_{\substack{d \in \mathbb{Z} \\ 0 \le d \le D}} F_t(d)

を求めてください。各バージョンで撮影日は独立に最適なものを選べます。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq D \leq 10^9
  • 0 \leq Q \leq 10^5
  • N(Q+1) \leq 5 \times 10^5
  • |X_i| \leq 10^6 (1 \leq i \leq N)
  • |V_i| \leq 10^6 (1 \leq i \leq N)
  • 1 \leq L_i \leq 10^6 (1 \leq i \leq N)
  • 1 \leq P_j \leq N (1 \leq j \leq Q)
  • |A_j| \leq 10^6 (1 \leq j \leq Q)
  • |B_j| \leq 10^6 (1 \leq j \leq Q)
  • 1 \leq C_j \leq 10^6 (1 \leq j \leq Q)
  • 入力はすべて整数である。
  • この制約下で、出力すべき値はすべて signed 64-bit integer に収まる。

入力

N D Q
X_1 V_1 L_1
X_2 V_2 L_2
:
X_N V_N L_N
P_1 A_1 B_1 C_1
P_2 A_2 B_2 C_2
:
P_Q A_Q B_Q C_Q
  • 1 行目には、山車の台数 N、撮影日として選べる最終日 D、修正回数 Q がスペース区切りで与えられる。
  • 続く N 行では、初期データが与えられる。
  • 1 + i 行目には、山車 i の 0 日目の中心座標 X_i、1 日あたりの移動速度 V_i、半幅 L_i がスペース区切りで与えられる。
  • 続く Q 行では、修正指示が時系列順に与えられる。
  • 1 + N + j 行目には、j 回目の修正を表す P_j, A_j, B_j, C_j がスペース区切りで与えられる。
  • これは、山車 P_j の初期座標を A_j、移動速度を B_j、半幅を C_j に置き換えることを意味する。この変更はバージョン j 以降すべてに反映される。

出力

G_0
G_1
:
G_Q

Q + 1 行出力せよ。1 + t 行目には、バージョン t における G_t を整数として出力せよ。

入力例 1

2 5 2
0 1 1
10 -1 2
1 2 0 1
2 5 1 1

出力例 1

4
6
5

入力例 2

3 4 0
0 0 1
5 -1 2
-3 2 1

出力例 2

5

入力例 3

6 30 5
-10 3 2
15 -2 3
0 0 1
25 -1 4
-20 4 2
8 1 5
3 5 -3 2
6 -5 2 1
1 12 -1 3
4 0 0 6
2 -15 5 2

出力例 3

24
34
34
34
20
20

入力例 4

12 1000000000 10
1000000 -1000000 1000000
-1000000 1000000 999999
0 500000 12345
500000 0 777777
-500000 -250000 333333
123456 654321 111111
-654321 -123456 222222
999999 -1 1
-999999 1 2
314159 -271828 31415
-271828 314159 92653
42 -42 1000000
1 -1000000 1000000 1
12 1000000 -1000000 1000000
6 0 0 500000
9 500000 500000 10
4 -999999 999999 999999
7 12345 -54321 123456
2 222222 -333333 444444
11 -1 1 1
5 1000000 0 1000000
10 -1000000 -1000000 999999

出力例 4

2361110
2361110
2361110
2361110
2361110
2083343
2083343
2083343
2083343
3000000
3999999

入力例 5

2 1 0
-1000000 -1000000 1000000
1000000 1000000 1000000

出力例 5

4000000

Score : 400 pts

Problem Statement

Takahashi is trying to photograph a parade of N floats moving along a straight road.

He will choose one shooting day from the integer days between day 0 and day D (inclusive). Takahashi wants to make the camera's frame width as small as possible while fitting all the floats in the frame.

The center coordinate of float i on day d is X_i + V_i \cdot d. Here, X_i is the center coordinate on day 0, and V_i is the movement speed per day (if negative, the float moves in the direction of decreasing coordinates). Float i has a half-width of L_i extending in both directions from its center, so it occupies the interval

[X_i + V_i \cdot d - L_i, \ X_i + V_i \cdot d + L_i]

on the road.

The frame width required to capture all floats on day d is

F(d) = \max_{1 \le i \le N}(X_i + V_i \cdot d + L_i) - \min_{1 \le i \le N}(X_i + V_i \cdot d - L_i)

However, Aoki has sent Q modification instructions regarding the parade operation plan. In the j-th modification, the initial coordinate, movement speed, and half-width of float P_j are changed to A_j, B_j, C_j respectively.

Let version 0 be the initial data, and version j (1 \le j \le Q) be the data obtained by applying the j-th modification to version j-1. Denoting the initial coordinate, movement speed, and half-width of float i in version t as X_i^{(t)}, V_i^{(t)}, L_i^{(t)} respectively, the frame width on day d in version t is

F_t(d) = \max_{1 \le i \le N}(X_i^{(t)} + V_i^{(t)} \cdot d + L_i^{(t)}) - \min_{1 \le i \le N}(X_i^{(t)} + V_i^{(t)} \cdot d - L_i^{(t)})

For each version t (0 \le t \le Q), find the minimum frame width when the shooting day is chosen optimally:

G_t = \min_{\substack{d \in \mathbb{Z} \\ 0 \le d \le D}} F_t(d)

The shooting day can be chosen independently and optimally for each version.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq D \leq 10^9
  • 0 \leq Q \leq 10^5
  • N(Q+1) \leq 5 \times 10^5
  • |X_i| \leq 10^6 (1 \leq i \leq N)
  • |V_i| \leq 10^6 (1 \leq i \leq N)
  • 1 \leq L_i \leq 10^6 (1 \leq i \leq N)
  • 1 \leq P_j \leq N (1 \leq j \leq Q)
  • |A_j| \leq 10^6 (1 \leq j \leq Q)
  • |B_j| \leq 10^6 (1 \leq j \leq Q)
  • 1 \leq C_j \leq 10^6 (1 \leq j \leq Q)
  • All input values are integers.
  • Under these constraints, all values to be output fit in a signed 64-bit integer.

Input

N D Q
X_1 V_1 L_1
X_2 V_2 L_2
:
X_N V_N L_N
P_1 A_1 B_1 C_1
P_2 A_2 B_2 C_2
:
P_Q A_Q B_Q C_Q
  • The first line contains the number of floats N, the last selectable shooting day D, and the number of modifications Q, separated by spaces.
  • The following N lines give the initial data.
  • The (1 + i)-th line contains the center coordinate X_i of float i on day 0, the movement speed per day V_i, and the half-width L_i, separated by spaces.
  • The following Q lines give the modification instructions in chronological order.
  • The (1 + N + j)-th line contains P_j, A_j, B_j, C_j representing the j-th modification, separated by spaces.
  • This means replacing the initial coordinate of float P_j with A_j, the movement speed with B_j, and the half-width with C_j. This change is reflected in version j and all subsequent versions.

Output

G_0
G_1
:
G_Q

Output Q + 1 lines. The (1 + t)-th line should contain G_t for version t as an integer.

Sample Input 1

2 5 2
0 1 1
10 -1 2
1 2 0 1
2 5 1 1

Sample Output 1

4
6
5

Sample Input 2

3 4 0
0 0 1
5 -1 2
-3 2 1

Sample Output 2

5

Sample Input 3

6 30 5
-10 3 2
15 -2 3
0 0 1
25 -1 4
-20 4 2
8 1 5
3 5 -3 2
6 -5 2 1
1 12 -1 3
4 0 0 6
2 -15 5 2

Sample Output 3

24
34
34
34
20
20

Sample Input 4

12 1000000000 10
1000000 -1000000 1000000
-1000000 1000000 999999
0 500000 12345
500000 0 777777
-500000 -250000 333333
123456 654321 111111
-654321 -123456 222222
999999 -1 1
-999999 1 2
314159 -271828 31415
-271828 314159 92653
42 -42 1000000
1 -1000000 1000000 1
12 1000000 -1000000 1000000
6 0 0 500000
9 500000 500000 10
4 -999999 999999 999999
7 12345 -54321 123456
2 222222 -333333 444444
11 -1 1 1
5 1000000 0 1000000
10 -1000000 -1000000 999999

Sample Output 4

2361110
2361110
2361110
2361110
2361110
2083343
2083343
2083343
2083343
3000000
3999999

Sample Input 5

2 1 0
-1000000 -1000000 1000000
1000000 1000000 1000000

Sample Output 5

4000000