Editorial for An Animal Contest 2 P5 - Koala Carnival

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.

Authors: sjay05, samliu12

Subtask 1

For each query from l to r, iterate r \le i \le N and find the furthest left endpoint \text{lft}[i] such that all stuffed animals from \text{lft}[i] to i are unique. We take the maximum of i - \text{lft}[i] + 1 for all \text{lft}[i] \le l.

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

Subtask 2

To optimize, we use a two pointer approach to determine \text{lft}[i] for all r \le i \le N 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 i - \text{lft}[i] + 1 for all \text{lft}[i] \le l.

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

Subtask 3

As before, we precompute \text{lft}[i] for all i (1 \le i \le N). By using the monotonic property of \text{lft}, the answer for query l_i, r_i can be found by binary searching for the rightmost index \text{pos} such that \text{lft}[\text{pos}] \le l_i. All k > \text{pos} have right endpoints higher than l_i. Thus, we only need the largest distinct subarray with the right endpoint in the range [r_i, \text{pos}]. We can perform this query using a range tree like a Segment Tree or a Sparse Table.

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

Comments


  • 1
    zenomyth  commented on Oct. 16, 2023, 3:28 p.m.

    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.