USACO

USACO 2022 US Open Contest, Platinum

Problem 3. Up Down Subsequence

Contest has ended.

Log in to allow submissions in analysis mode

Farmer John's $N$ cows ( $2 \leq N \leq 3\cdot 10^5$ ), conveniently numbered $1 \ldots N$ as usual, have ordered themselves according to 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. Please find the maximum $K\le N-1$ such that there exists a subsequence $a_0,a_1,\ldots,a_{K}$ of $p$ such that for all $1\le j\le K$ , $a_{j - 1} < a_j$ if the $j$ th letter in the string is U, and $a_{j - 1} > a_j$ if the $j$ th letter in the string is D.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains

$N$ .

The second line contains $p_1,p_2,\ldots,p_N$ .

The last line contains the string.

OUTPUT FORMAT (print output to the terminal / stdout):

Write out maximum possible value of

$K$ .

SAMPLE INPUT:

5
1 5 3 4 2
UDUD

SAMPLE OUTPUT:

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 is consistent with the string.

SAMPLE INPUT:

5
1 5 3 4 2
UUDD

SAMPLE OUTPUT:

We can choose $[a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]$ .

SCORING:

Test cases 3-4 satisfy $N\le 500$ .
Test cases 5-8 satisfy $N\le 5000$ .
In test cases 9-12, the string consists of Us followed by Ds.
Test cases 13-22 satisfy no additional constraints.

Problem credits: Danny Mittal

Contest has ended. No further submissions allowed.