Ex - Linear Maximization Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 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