P9180 [COCI 2022/2023 #5] Slastičarnica

There is a sequence $a_1,\ldots,a_n$ and $q$ operations. Each operation is of the form: “Delete a prefix or suffix of length $d_i$, and you must ensure that all elements in this prefix or suffix are greater than or equal to $s_i$.” Before each operation, you may choose a prefix and/or suffix of any length (they can be empty, and you may choose both ends at the same time) and delete them. If at some operation it cannot be performed, then this operation and all following operations stop. Ask for the maximum number of operations that can be performed.

The first line contains two positive integers $n,q\ (1\le n\le 5\ 000,1\le q\le 2\cdot 10^5)$, representing the sequence length and the number of operations. The second line contains $n$ positive integers $a_i\ (1\le a_i\le 10^9)$, representing the sequence. The next $q$ lines each contain two integers $d_i,s_i\ (1\le d_i\le n,1\le s_i\le 10^9)$, describing one operation.

Output one line with one integer, representing the maximum number of operations that can be performed.

Explanation for sample $3$: First delete the prefix $(1)$, then perform the first operation and delete the prefix $(3,2,5)$. The sequence becomes $(1,4,6,2,1)$. Then delete the prefix $(1)$, then perform the second operation and delete the prefix $(4,6)$. The sequence becomes $(2,1)$. Then do not delete any prefix or suffix, perform the third operation, and delete the suffix $(1)$. The sequence becomes $(2)$. Then do not delete any prefix or suffix, perform the fourth operation, and delete the only remaining $(2)$. The sequence becomes empty. The last operation cannot be completed because the sequence is empty, so the operations stop. Therefore, a total of four operations are performed. |Subtask ID|Additional Constraints|Score| |:-:|:-:|:-:| |$0$|Sample only|$0$| |$1$|$n,q\le 100$|$19$| |$2$|$d_1=d_2=\ldots=d_q=1$|$28$| |$3$|No additional constraints|$53$| Translated by ChatGPT 5