Editorial for Wesley's Anger Contest 5 Problem 2 - MATH 137 at Squirreloo


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

Subtask 1

Since N,Q \le 5\,000, for each query we can simply iterate over the array in reverse order, breaking when we find an element that lies outside the range [L-\epsilon, L+\epsilon].

Time Complexity: \mathcal{O}(NQ)

Subtask 2

The intended solution for this subtask is to maintain a suffix min and suffix max array and then binary search for the longest suffix for which the maximum and minimum elements of the suffix lie in the range [L-\epsilon, L+\epsilon]. This requires \mathcal{O}(N) preprocessing to create the suffix min/max arrays and then a \mathcal{O}(\log N) binary search for each query.

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


Comments

There are no comments at the moment.