题目详情题解（0）讨论（0）提交记录（0）

AT_abc244_h.[ABC244Ex] Linear Maximization

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在二维平面上有一个点集 SS，初始时 SS 为空。

请依次处理 i=1,2,…,Qi = 1, 2, \dots, Q 的以下查询：

  • 给定整数 Xi,Yi,Ai,BiX_i, Y_i, A_i, B_i。在 SS 中加入点 (Xi,Yi)(X_i, Y_i) 后，求 max⁡(x,y)∈S{Aix+Biy}\displaystyle\max_{(x, y) \in S} \left\{A_i x + B_i y\right\} 的值。

输入格式

输入以如下格式从标准输入给出。

QQ X1X_1 Y1Y_1 A1A_1 B1B_1 X2X_2 Y2Y_2 A2A_2 B2B_2 ⋮\vdots XQX_Q YQY_Q AQA_Q BQB_Q

输出格式

输出共 QQ 行。第 ii 行输出第 ii 个查询的答案。

输入输出样例

  • 输入#1

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

    输出#1

    -1
2
1
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

说明/提示

限制条件

  • 所有输入均为整数。
  • 1≤Q≤2×1051 \leq Q \leq 2 \times 10^5
  • ∣Xi∣,∣Yi∣,∣Ai∣,∣Bi∣≤109|X_i|, |Y_i|, |A_i|, |B_i| \leq 10^9
  • 若 i≠ji \neq j，则 (Xi,Yi)≠(Xj,Yj)(X_i, Y_i) \neq (X_j, Y_j)。

样例解释 1

  • 当 i=1i = 1 时：向 SS 中加入点 (1,0)(1, 0)，此时 S={(1,0)}S = \{(1, 0)\}。当 (x,y)=(1,0)(x, y) = (1, 0) 时，−x−y=−1-x - y = -1，这是最大值。
  • 当 i=2i = 2 时：向 SS 中加入点 (0,1)(0, 1)，此时 S={(0,1),(1,0)}S = \{(0, 1), (1, 0)\}。当 (x,y)=(1,0)(x, y) = (1, 0) 时，2x=22x = 2，这是最大值。
  • 当 i=3i = 3 时：向 SS 中加入点 (−1,0)(-1, 0)，此时 S={(−1,0),(0,1),(1,0)}S = \{(-1, 0), (0, 1), (1, 0)\}。当 (x,y)=(1,0)(x, y) = (1, 0) 或 (x,y)=(0,1)(x, y) = (0, 1) 时，x+y=1x + y = 1，这是最大值。
  • 当 i=4i = 4 时：向 SS 中加入点 (0,−1)(0, -1)，此时 S={(−1,0),(0,−1),(0,1),(1,0)}S = \{(-1, 0), (0, -1), (0, 1), (1, 0)\}。当 (x,y)=(0,−1)(x, y) = (0, -1) 时，x−2y=2x - 2y = 2，这是最大值。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页