Editorial for An Animal Contest 2 P5 - Koala Carnival - Olympiads Online Judge

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$ $l$ to $r$ $r$ , iterate $r \le i \le N$ $r \leq i \leq N$ and find the furthest left endpoint $\text{lft}[i]$ $lft [i]$ such that all stuffed animals from $\text{lft}[i]$ $lft [i]$ to $i$ $i$ are unique. We take the maximum of $i - \text{lft}[i] + 1$ $i - lft [i] + 1$ for all $\text{lft}[i] \le l$ $lft [i] \leq l$ .

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

Subtask 2

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

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

Subtask 3

As before, we precompute $\text{lft}[i]$ $lft [i]$ for all $i$ $i$ $(1 \le i \le N)$ $(1 \leq i \leq N)$ . By using the monotonic property of $\text{lft}$ $lft$ , the answer for query $l_i, r_i$ $l_{i}, r_{i}$ can be found by binary searching for the rightmost index $\text{pos}$ $pos$ such that $\text{lft}[\text{pos}] \le l_i$ $lft [pos] \leq l_{i}$ . All $k > \text{pos}$ $k > pos$ have right endpoints higher than $l_i$ $l_{i}$ . Thus, we only need the largest distinct subarray with the right endpoint in the range $[r_i, \text{pos}]$ $[r_{i}, 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)$ $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.