Ex - Linear Maximization

AtCoder

IDabc244_h

Time5000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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.

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

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Ex - Linear Maximization",
    "description": {
      "content": "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$, ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc244_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a set $S$ of points on a two-dimensional plane. $S$ is initially empty.\nFor each $i = 1, 2, \\dots, Q$ in this order, process the following query.\n\n*   You are given integers $X_i, Y_i, A_i$, ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments