P8818 [CSP-S 2022] Strategy Game

Xiao L and Xiao Q are playing a strategy game. Given an array $A$ of length $n$ and an array $B$ of length $m$, define an $n \times m$ matrix $C$ such that $C_{i j} = A_i \times B_j$. All indices start from $1$. The game has $q$ rounds. In each round, $4$ parameters $l_1, r_1, l_2, r_2$ are given in advance, satisfying $1 \le l_1 \le r_1 \le n$ and $1 \le l_2 \le r_2 \le m$. In the game, Xiao L first chooses an index $x$ between $l_1 \sim r_1$, and then Xiao Q chooses an index $y$ between $l_2 \sim r_2$. The score of this round is defined as $C_{x y}$. Xiao L’s goal is to make this score as large as possible, while Xiao Q’s goal is to make it as small as possible. Both players are sufficiently smart and always use optimal strategies. Question: Under both players’ optimal strategies, what is the score in each round?

The first line contains three positive integers $n$, $m$, $q$, representing the lengths of array $A$, array $B$, and the number of game rounds. The second line contains $n$ integers $A_i$, the elements of array $A$. The third line contains $m$ integers $B_i$, the elements of array $B$. Then follow $q$ lines. Each line contains four positive integers, representing $l_1, r_1, l_2, r_2$ for this round.

Output $q$ lines. Each line contains one integer, representing the score in that round under the players’ optimal strategies.

**Sample Explanation #1** In this dataset, the matrix $C$ is as follows: $$ \begin{bmatrix} 0 & 0 \\ -3 & 4 \\ 6 & -8 \end{bmatrix} $$ In the first round, no matter whether Xiao L chooses $x = 2$ or $x = 3$, Xiao Q can choose some $y$ to make the final score negative. Therefore, choosing $x = 1$ is optimal for Xiao L, because then the score is guaranteed to be $0$. In the second round, since Xiao L can choose $x = 2$, Xiao Q can only choose $y = 2$, so the score is $4$. **Sample #3** See the attachments `game/game3.in` and `game/game3.ans`. **Sample #4** See the attachments `game/game4.in` and `game/game4.ans`. **Constraints** For all testdata, $1 \le n, m, q \le {10}^5$, $-{10}^9 \le A_i, B_i \le {10}^9$. For each round, $1 \le l_1 \le r_1 \le n$, $1 \le l_2 \le r_2 \le m$. | Test point ID | $n, m, q \le$ | Special condition | |:-:|:-:|:-:| | $1$ | $200$ | 1, 2 | | $2$ | $200$ | 1 | | $3$ | $200$ | 2 | | $4 \sim 5$ | $200$ | None | | $6$ | $1000$ | 1, 2 | | $7 \sim 8$ | $1000$ | 1 | | $9 \sim 10$ | $1000$ | 2 | | $11 \sim 12$ | $1000$ | None | | $13$ | ${10}^5$ | 1, 2 | | $14 \sim 15$ | ${10}^5$ | 1 | | $16 \sim 17$ | ${10}^5$ | 2 | | $18 \sim 20$ | ${10}^5$ | None | Here, special property 1: guarantee $A_i, B_i > 0$. Special property 2: guarantee that for each round, either $l_1 = r_1$ or $l_2 = r_2$. Translated by ChatGPT 5