/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
数列 A = (A_1,\dots,A_N) があります。A の部分列であって、数列 B = (B_1,\dots,B_M) と一致するものが 2 つ以上あるかどうかを判定してください。ただし、2 つの部分列が数列として一致していても、取り出す位置が異なれば区別するものとします。
部分列とは
A の部分列とは、A の要素を 0 個以上選んで削除し、残った要素を元の順序を保って並べた数列のことを指します。制約
- 1 \leq M \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
A の部分列であって、数列 B と一致するものが 2 つ以上ある場合は Yes、そうでない場合は No を出力せよ。
入力例 1
4 2 1 2 1 2 1 2
出力例 1
Yes
A の部分列であって B と一致するものは、(A_1,A_2),(A_1,A_4),(A_3,A_4) の 3 つです。
入力例 2
3 2 1 2 1 1 2
出力例 2
No
A の部分列であって B と一致するものは、(A_1,A_2) のみです。
入力例 3
3 2 1 1 2 2 1
出力例 3
No
A の部分列であって B と一致するものはありません。
Score : 400 points
Problem Statement
There is a sequence A = (A_1,\dots,A_N). Determine whether there are at least two subsequences of A that match the sequence B = (B_1,\dots,B_M). Two subsequences are distinguished if they are taken from different positions, even if they coincide as sequences.
Subsequence
A subsequence of A is a sequence obtained by removing zero or more elements from A and leaving the remaining elements in their original order.Constraints
- 1 \leq M \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
If there are at least two subsequences of A that match B, print Yes. Otherwise, print No.
Sample Input 1
4 2 1 2 1 2 1 2
Sample Output 1
Yes
There are three subsequences of A that match B: (A_1,A_2), (A_1,A_4), (A_3,A_4).
Sample Input 2
3 2 1 2 1 1 2
Sample Output 2
No
There is only one subsequence of A that matches B: (A_1,A_2).
Sample Input 3
3 2 1 1 2 2 1
Sample Output 3
No
There are no subsequences of A that match B.