No.1804 Intersection of LIS
タグ : / 解いたユーザー数 61
作問者 :
nok0
penguinman
Problem Statement
You are given a sequence $P=(P_1,P_2,\dots,P_N)$ that is a permutation of $(1,2,\dots,N)$. $P$ may have several possible LIS (longest increasing subsequences). Enumerate the elements that are contained in all of them.
Input
$N$ $P_1$ $P_2$ $\ldots$ $P_N$
- All input values are integers.
- $1 \leq N \leq 3 \times 10^5$
- $P$ is a permutation of $(1,2,\dots,N)$.
Output
First, on line $1$, print the number of elements contained in all LIS of $P$.
Then, on line $2$, print the elements contained in all LIS of $P$, separated by spaces, in ascending order of index. If the number of elements is $0$, print an empty line as line $2$.
Finally, print a newline.
Sample
Sample 1
Input
5 1 4 3 2 5
Output
2 1 5
There are $3$ possible LIS: $(A_1,A_2,A_5)=(1,4,5), \ (A_1,A_3,A_5)=(1,3,5), \ (A_1,A_4,A_5)=(1,2,5)$.
The elements contained in all of these are $A_1 = 1, A_5 = 5$, so print them.
Sample 2
Input
3 2 3 1
Output
2 2 3
The only LIS is $(A_1,A_2)=(2,3)$.
Sample 3
Input
6 4 5 6 1 2 3
Output
0
The number of elements contained in all LIS may be $0$. In such a case, do not forget to print an empty line as line $2$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。