AtCoder Beginner Contest 244
翻译中…
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.
翻译中…
样例
Input #1
4
1 0 -1 -1
0 1 2 0
-1 0 1 1
0 -1 1 -2
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
0
35
31
21
36
87
0
36
31
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。