Editorial for DMOPC '17 Contest 1 P5 - Intimidating Arrays - Olympiads Online Judge

Editorial for DMOPC '17 Contest 1 P5 - Intimidating Arrays

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

For the first subtask, we can find the intimidation value of a subarray by looping through it, and increasing a counter if the current element is larger than all elements before it.

Time Complexity: $\mathcal O(QN)$ $O (Q N)$

For the second subtask, we can sort the queries by descending $l$ $l$ value. As we loop through $A$ $A$ from right to left, we can keep a monotonically increasing stack to keep track of which values to the right of the current value are greater than it. We can maintain this stack in amortized $\mathcal O(1)$ $O (1)$ time. The intimidation value of an array is thus the number of elements in said stack which are less than the current query's $r$ $r$ value. This can be computed in $\mathcal O(\log N)$ $O (\log N)$ time with a Binary Indexed Tree.

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

Comments

There are no comments at the moment.