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)

Subtask 2

Notice for each type of query:

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

  • If the array 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). The maximal value is: \max(y_n, x_w).

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

  • If the array 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). The minimal value is: \max(y_1, x_w).

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

  • If the array 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). The maximal value is: \max(x_n, y_w).

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

  • If the array 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). The minimal value is: \max(x_1, y_w).

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

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


Comments

There are no comments at the moment.