問題一覧 > 通常問題

No.3465 Lis! Lis! Lis!

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 2
作問者 : tyawanmusi / テスター : dyktr_06 hikikomori
お気に入りにしたユーザー ProblemId : 12950 / 自分の提出
問題文最終更新日: 2026-02-15 20:13:31
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 021 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。