結果

問題 No.3465 Lis! Lis! Lis!
コンテスト
ユーザー tyawanmusi
提出日時 2026-02-15 19:20:26
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 441 ms / 2,000 ms
コード長 1,716 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 220 ms
コンパイル使用メモリ 77,816 KB
実行使用メモリ 163,556 KB
最終ジャッジ日時 2026-02-28 13:07:38
合計ジャッジ時間 9,751 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n, m = map(int, input().split())
# cnt[i] ... Ai を含む区間の LIS の最小値
cnt = [n] * n
# edge ... 最小単位の区間列挙
edge = {0, n}

lrk = []
for _ in range(m):
    l, r, k = map(int, input().split())
    l -= 1
    lrk.append((l, r, k))
    edge.add(l)
    edge.add(r)
    for i in range(l, r):
        cnt[i] = min(cnt[i], k)

edge = sorted(edge)
edge_idx = {e: i for i, e in enumerate(edge)}
# cnt を圧縮
# 最小単位の区間、その区間が取る LIS をまとめる
cnt_comp = [cnt[i] for i in edge[:-1]]
for i in range(len(cnt_comp)):
    length = edge[i + 1] - edge[i]
    cnt_comp[i] = min(cnt_comp[i], length)

# 各区間 [l:r) について LIS が k となるように最小単位の区間に値を割り振る
# i 番目の最小単位の区間の要素が i-1 番目の区間の要素より diff[i] だけ大きくなるように
# LIS([edge[i - 1]:edge[i]]) + diff[i] = LIS([edge[i - 1]:edge[i + 1]])
diff = [0] * len(cnt_comp)
for l, r, k in lrk:
    li = edge_idx[l]
    ri = edge_idx[r]
    if sum(cnt_comp[li:ri]) < k:
        exit(print("No"))

    remain = k - cnt_comp[li]
    for i in range(li + 1, ri):
        diff[i] = min(cnt_comp[i], remain)
        remain -= diff[i]
    if remain:
        exit(print("No"))

# 構築
# 最小単位の区間内は 1234444... のように構成する
# diff を参考に構成し、最後に 1~N で埋める
ans = [1] * n
current = 1
for i in range(len(cnt_comp)):
    use = 0
    if i != 0:
        use = ans[edge[i] - 1] - cnt_comp[i] + diff[i]
    for j in range(edge[i], edge[i + 1]):
        ans[j] = min(j - edge[i] + 1, cnt_comp[i]) + use
mi = min(ans)
for i in range(n):
    ans[i] += 1 - mi

print("Yes")
print(*ans)
0