Editorial for DMOPC '20 Contest 2 P2 - Lousy Christmas Presents


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: richardzhang

Subtask 1

For every query, iterate through all the colours and find the first occurrence of a_i and the last occurrence of b_i.

The answer is given by \max_{1 \le i \le M} \{\mathrm {last} (b_i) - \mathrm {first} (a_i) \textrm { if } b_i \textrm{ and } a_i \textrm{ are colours that exist in the scarf}\}.

Time complexity: \mathcal O(NM)

Subtask 2

There is no intended solution. (Red herring task.)

Time complexity: \mathcal O(NM)

Subtask 3

Keep track of the first and last occurrence of every colour. For every query, it's now possible to query \mathrm {first}(i) and \mathrm {last}(i) in \mathcal O(1). The rest of the solution follows from Subtask 1.

Time complexity: \mathcal O(N + M)


Comments

There are no comments at the moment.