No.3465 Lis! Lis! Lis!
タグ : / 解いたユーザー数 2
作問者 :
hikikomori
Problem Statement
You are given a positive integer $N$ and $M$ tuples of integers $(l_i, r_i, k_i)\ (1\le i\le M)$. Each tuple satisfies $1\le l_i < r_i \le N$ and $1\le k_i \le N$.
Furthermore, for any integer $p\ (1\le p\le N)$, at most $2$ tuples $(l_i, r_i, k_i)$ satisfy the condition $l_i \le p \le r_i$.
Construct one sequence $A$ of length $N$ that satisfies the following conditions. If no such construction is possible, report that fact.
- $1 \le A_i \le N$
- For every $i\ (1\le i\le M)$, the length of the longest strictly increasing subsequence (LIS) of the contiguous subarray $(A_{l_i},A_{l_i+1},\cdots,A_{r_i})$ of $A$ is exactly $k_i$.
Constraints
- All input values are integers.
- $2 \le N \le 2\times10^5$
- $1 \le M \le N-1$
- $1\le l_i < r_i \le N$
- $1\le k_i \le N$
- For any integer $p\ (1\le p\le N)$, at most $2$ tuples $(l_i, r_i, k_i)$ satisfy $l_i \le p \le r_i$.
Input
The input is given from Standard Input in the following format.
$N\ M$ $l_1\ r_1\ k_1$ $l_2\ r_2\ k_2$ $\vdots$ $l_M\ r_M\ k_M$
Output
If a construction is possible, print Yes on the first line as shown below. Then, print the constructed sequence $A$ on the second line, separated by spaces.
Yes $A_1\ A_2\ \cdots\ A_N$
If a construction is impossible, print No on the first line as shown below.
No
Print a newline at the end.
Sample
Sample 1
Input
6 4 1 3 2 4 6 2 2 4 3 5 6 1
Output
Yes 2 1 2 4 6 5
- $(A_1,A_2,A_3)=(2,1,2)$ and the length of its LIS is $2$, so this output satisfies the condition given by $(l_1,r_1,k_1)$.
- $(A_2,A_3,A_4)=(1,2,4)$ and the length of its LIS is $3$, so this output satisfies the condition given by $(l_3,r_3,k_3)$.
The other two conditions are also satisfied, so this output is correct. Another valid answer is, for example, $A=(1,1,2,3,4,4)$.
Sample 2
Input
5 3 1 5 5 1 2 1 4 5 2
Output
No
No sequence $A$ satisfying the conditions exists.
Sample 3
Input
10 5 1 8 6 1 2 2 4 5 2 6 9 1 9 10 2
Output
Yes 1 2 3 4 5 6 6 6 6 7
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。