Ex - Linear Maximization Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

2 次元平面上の点の集合 S があります。S ははじめ空です。

i = 1, 2, \dots, Q の順に、以下のクエリを処理してください。

  • 整数 X_i, Y_i, A_i, B_i が与えられる。S に点 (X_i, Y_i) を追加した後、\displaystyle \max_{(x,y) \in S}\left\{A_ix + B_iy\right\} を求める。

制約

  • 入力は全て整数
  • 1≤Q≤2 \times 10^5
  • |X_i|, |Y_i|, |A_i|, |B_i|≤10^9
  • i ≠ j ならば (X_i, Y_i)≠(X_j, Y_j)

入力

入力は以下の形式で標準入力から与えられる。

Q
X_1 Y_1 A_1 B_1
X_2 Y_2 A_2 B_2
\vdots
X_Q Y_Q A_Q B_Q

出力

Q 行出力せよ。i 行目には、i 個目のクエリに対する答えを出力せよ。

入力例 1

4
1 0 -1 -1
0 1 2 0
-1 0 1 1
0 -1 1 -2

出力例 1

-1
2
1
2
  • i = 1 のとき : S に点 (1, 0) を追加し、S = \{(1, 0)\} とします。(x, y) = (1, 0) のとき -x - y = -1 となり、これが最大値を取ります。
  • i = 2 のとき : S に点 (0, 1) を追加し、S = \{(0, 1), (1, 0)\} とします。(x, y) = (1, 0) のとき 2x = 2 となり、これが最大値を取ります。
  • i = 3 のとき : S に点 (-1, 0) を追加し、S = \{(-1, 0), (0, 1), (1, 0)\} とします。(x, y) = (1, 0) または (x, y) = (0, 1) のとき x + y = 1 となり、これが最大値を取ります。
  • i = 4 のとき : S に点 (0, -1) を追加し、S = \{(-1, 0), (0, -1), (0, 1), (1, 0)\} とします。(x, y) = (0, -1) のとき x - 2y = 2 となり、これが最大値を取ります。

入力例 2

9
-1 4 -8 -2
9 -9 -7 7
4 1 6 7
-4 -1 -4 -5
-9 3 -2 -6
-1 0 -8 5
-8 -5 0 0
8 3 0 -4
2 -5 2 5

出力例 2

0
35
31
21
36
87
0
36
31

Score : 600 points

Problem Statement

There is a set S of points on a two-dimensional plane. S is initially empty.

For each i = 1, 2, \dots, Q in this order, process the following query.

  • You are given integers X_i, Y_i, A_i, and B_i. Add point (X_i, Y_i) to S, and then find \displaystyle \max_{(x,y) \in S}\left\{A_ix + B_iy\right\}.

Constraints

  • All values in input are integers.
  • 1≤Q≤2 \times 10^5
  • |X_i|, |Y_i|, |A_i|, |B_i| ≤10^9
  • If i ≠ j, then (X_i, Y_i) ≠ (X_j, Y_j).

Input

Input is given from Standard Input in the following format:

Q
X_1 Y_1 A_1 B_1
X_2 Y_2 A_2 B_2
\vdots
X_Q Y_Q A_Q B_Q

Output

Print Q lines. The i-th line should contain the answer for the i-th query.

Sample Input 1

4
1 0 -1 -1
0 1 2 0
-1 0 1 1
0 -1 1 -2

Sample Output 1

-1
2
1
2
  • When i = 1: add point (1, 0) to S, then it will become S = \{(1, 0)\}. For (x, y) = (1, 0), we have -x - y = -1, which is the maximum.
  • When i = 2: add point (0, 1) to S, then it will become S = \{(0, 1), (1, 0)\}. For (x, y) = (1, 0), we have 2x = 2, which is the maximum.
  • When i = 3: add point (-1, 0) to S, then it will become S = \{(-1, 0), (0, 1), (1, 0)\}. For (x, y) = (1, 0) or (x, y) = (0, 1), we have x + y = 1, which is the maximum.
  • When i = 4: add point (0, -1) to S, then it will become S = \{(-1, 0), (0, -1), (0, 1), (1, 0)\}. For (x, y) = (0, -1), we have x - 2y = 2, which is the maximum.

Sample Input 2

9
-1 4 -8 -2
9 -9 -7 7
4 1 6 7
-4 -1 -4 -5
-9 3 -2 -6
-1 0 -8 5
-8 -5 0 0
8 3 0 -4
2 -5 2 5

Sample Output 2

0
35
31
21
36
87
0
36
31