Editorial for QCC P2 - Online School - Olympiads Online Judge

Editorial for QCC P2 - Online School

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: sjay05

Subtask 1

Brute force suffices.

Time Complexity: $\mathcal{O}(NQ)$ $O (N Q)$

Subtask 2

Notice for each type of query:

1 w: denotes $\max(\max_{i=1}^n y_i, x_w)$ $max ({max}_{i = 1}^{n} y_{i}, x_{w})$ .

If the array $y$ $y$ is sorted, the values in the column are ordered as: $\max(y_1, x_w) \le \max(y_2, x_w) \le \dots \le \max(y_n, x_w)$ $max (y_{1}, x_{w}) \leq max (y_{2}, x_{w}) \leq \dots \leq max (y_{n}, x_{w})$ . The maximal value is: $\max(y_n, x_w)$ $max (y_{n}, x_{w})$ .

2 w: denotes $\max(\min_{i=1}^n y_i, x_w)$ $max ({min}_{i = 1}^{n} y_{i}, x_{w})$ .

If the array $y$ $y$ is sorted, the values in the column are ordered as: $\max(y_1, x_w) \le \max(y_2, x_w) \le \dots \le \max(y_n, x_w)$ $max (y_{1}, x_{w}) \leq max (y_{2}, x_{w}) \leq \dots \leq max (y_{n}, x_{w})$ . The minimal value is: $\max(y_1, x_w)$ $max (y_{1}, x_{w})$ .

3 w: denotes $\max(\max_{i=1}^n x_i, y_w)$ $max ({max}_{i = 1}^{n} x_{i}, y_{w})$ .

If the array $x$ $x$ is sorted, the values in the row are ordered as: $\max(x_1, y_w) \le \max(x_2, y_w) \le \dots \le \max(x_n, y_w)$ $max (x_{1}, y_{w}) \leq max (x_{2}, y_{w}) \leq \dots \leq max (x_{n}, y_{w})$ . The maximal value is: $\max(x_n, y_w)$ $max (x_{n}, y_{w})$ .

4 w: denotes $\max(\min_{i=1}^n x_i, y_w)$ $max ({min}_{i = 1}^{n} x_{i}, y_{w})$ .

If the array $x$ $x$ is sorted, the values in the row are ordered as: $\max(x_1, y_w) \le \max(x_2, y_w) \le \dots \le \max(x_n, y_w)$ $max (x_{1}, y_{w}) \leq max (x_{2}, y_{w}) \leq \dots \leq max (x_{n}, y_{w})$ . The minimal value is: $\max(x_1, y_w)$ $max (x_{1}, y_{w})$ .

The $\max$ $max$ and $\min$ $min$ of arrays $x$ $x$ and $y$ $y$ can be found in $\mathcal{O}(N)$ $O (N)$ time and stored before answering any queries.

Time Complexity: $\mathcal{O}(N+Q)$ $O (N + Q)$

Comments

There are no comments at the moment.