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$ ~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]$ ~[L-\epsilon, L+\epsilon]~.

Time Complexity: $\mathcal{O}(NQ)$ ~\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]$ ~[L-\epsilon, L+\epsilon]~. This requires $\mathcal{O}(N)$ ~\mathcal{O}(N)~ preprocessing to create the suffix min/max arrays and then an $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~ binary search for each query.

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

Comments

There are no comments at the moment.