P8277 [USACO22OPEN] Up Down Subsequence P

Farmer John has $N$ cows ($2 \leq N \leq 3\cdot 10^5$), numbered $1 \ldots N$, arranged into a permutation $p_1,p_2,\ldots,p_N$ of $1\ldots N$. You are also given a string of length $N-1$ consisting of the letters U and D. Find the largest $K\le N-1$ such that there exists a subsequence $a_0,a_1,\ldots,a_{K}$ of $p$ satisfying, for all $1\le j\le K$, if the $j$-th character of the string is U then $a_{j - 1} < a_j$, and if the $j$-th character is D then $a_{j - 1} > a_j$.

The first line contains $N$. The second line contains $p_1,p_2,\ldots,p_N$. The last line contains the given string.

Output the maximum possible value of $K$.

【Sample Explanation 1】 We can choose $[a_0,a_1,a_2,a_3,a_4]=[p_1,p_2,p_3,p_4,p_5]$; the entire permutation matches the given string. 【Sample Explanation 2】 We can choose $[a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]$. 【Test Point Properties】 - Test points 3-4 satisfy $N\le 500$. - Test points 5-8 satisfy $N\le 5000$. - In test points 9-12, all U in the string appear before all D. - Test points 13-22 have no additional constraints. Translated by ChatGPT 5