Editorial for An Animal Contest 2 P5 - Koala Carnival
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors:
,Subtask 1
For each query from to , iterate and find the furthest left endpoint such that all stuffed animals from to are unique. We take the maximum of for all .
Time Complexity:
Subtask 2
To optimize, we use a two pointer approach to determine for all in linear time, moving the right pointer backward only when a non-unique stuffed animal is reached and updating a count array accordingly.
As we did before, we take the maximum of for all .
Time Complexity:
Subtask 3
As before, we precompute for all . By using the monotonic property of , the answer for query can be found by binary searching for the rightmost index such that . All have right endpoints higher than . Thus, we only need the largest distinct subarray with the right endpoint in the range . We can perform this query using a range tree like a Segment Tree or a Sparse Table.
Time Complexity:
Comments
One doubt here: how do you search for duplicates? The only method I can think of is using map which consumes an additional log(N) time for each search.