Kattis is having a baby! O.o. However, she does not know
what to name her baby. Thankfully, her friends have many ideas,
giving suggestions for both genders.
Given $\textbf{N}$ distinct baby name suggestions (each babyName string consists of only UPPERCASE alphabet characters of no more than $30$ characters) and the genderSuitability of that name (integer $\textbf{1}$ for $\textbf{male}$ or integer $\textbf{2}$ for $\textbf{female}$) and given $\textbf{Q}$ queries, tell Kattis how many baby names start with a prefix that is inside a given query interval $[\textbf{start} \ldots \textbf{end})$, where $\textbf{start} < \textbf{end}$, and both are strings.
Note: A prefix of a string $T = T_{0}T_{1} \ldots T_{n-1}$ is
string $P = T_{0}T_{1} \ldots
T_{m-1}$ where $m \le
n$
There will be $4$ types of commands:
Stop: This will be indicated by a $0$. Stop your program upon encountering this.
Add Suggestion: This will be indicated by a starting integer $1$ followed by a string babyName and an integer genderSuitability, e.g. $1$ SIMBA $1$.
Remove Suggestion: This will be indicated by a starting integer $2$ followed by a string: babyName, e.g. $2$ SIMBA. The babyName is guaranteed to have already been suggested earlier.
Query: This will be indicated by a starting integer $3$ followed by two strings: start, end, and an integer genderSuitability. Your job is to return the number of names that is inside the interval $[\textbf{start} \ldots \textbf{end})$ subject to the following criteria.
If genderSuitability = $0$: report number of names for both genders
If genderSuitability = $1$: report number of male names
If genderSuitability = $2$: report number of female names
Each line will be a certain command. The program terminates when it encounters $0$. There are up to $200\, 000$ babyName suggestions and $Q$ is up to $500\, 000$.
Each time the $\textbf{Query}$ command is encountered, the number of suitable names should be printed.
$\textbf{(30 points)}$: $1 \le N \le 20$, $1 \le Q \le 10$, and all baby names have distinct first letters
$\textbf{(30 points)}$: $1 \le N \le 20\, 000$, $1 \le Q \le 20\, 000$
$\textbf{(40 points)}$: $1 \le N \le 200\, 000$, $1 \le Q \le 500\, 000$
Sample Input 1 | Sample Output 1 |
---|---|
1 KATTISJR 2 1 OLIVER 1 1 SIMBA 1 3 A Z 0 3 A Z 1 3 A Z 2 2 SIMBA 3 A Z 0 3 A Z 1 3 A Z 2 0 |
3 2 1 2 1 1 |