Editorial for SAC '22 Code Challenge 5 Junior P3 - Media List - Olympiads Online Judge

Editorial for SAC '22 Code Challenge 5 Junior P3 - Media List

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

Subtask 1

Maintain a set of distinct names with a built-in data structure provided in your language (e.g., set<int> for C++).

For each type $1$ $1$ query, output 1 if the set contains $name$ $n a m e$ or 0 if it does not.

For each type $2$ $2$ query, insert $name$ $n a m e$ into the set.

Note that a dynamic array is insufficient since $name$ $n a m e$ could be at the end of the array for type $1$ $1$ queries and blow up the solution to $\mathcal{O}(Q^2)$ $O (Q^{2})$ .

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

Subtask 2

Instead of using one set, define an array of $N$ $N$ sets.

The same logic as subtask $1$ $1$ applies.

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

Comments

There are no comments at the moment.