#1148280 (PyPy3) No.3465 Lis! Lis! Lis!

• 問題: No.3465 Lis! Lis! Lis!
• ユーザー: tyawanmusi
• 提出日時: 2026-02-15 20:10:04
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 763 ms / 2,000 ms
• コード長: 6,081 bytes
• コンパイル時間: 397 ms
• コンパイル使用メモリ: 78,104 KB
• 実行使用メモリ: 188,860 KB
• 最終ジャッジ日時: 2026-02-28 13:07:49
• 合計ジャッジ時間: 12,373 ms
• ジャッジサーバーID （参考情報）: judge1 / judge7

ファイルパターン	結果
sample	AC * 3
other	AC * 35

ソースコード

import sys

class InputError(Exception):
    pass

class StrictIn:

    def __init__(self, s: bytes, i: int = 0, line: int = 1, col: int = 1):
        self.s = s
        self.i = i
        self.line = line
        self.col = col

    @staticmethod
    def from_stdin_ascii() -> "StrictIn":
        raw = sys.stdin.buffer.read()
        for p, b in enumerate(raw):
            if b >= 0x80:
                raise InputError(f"non-ASCII byte at offset {p}: 0x{b:02x}")
            if b in (0x09, 0x0A, 0x0D):
                continue
            if 0x20 <= b <= 0x7E:
                continue
            raise InputError(f"disallowed control byte at offset {p}: 0x{b:02x}")
        return StrictIn(raw)

    def _eof(self) -> bool:
        return self.i >= len(self.s)

    def _peek(self):
        return None if self._eof() else self.s[self.i]

    def _advance(self) -> int:
        if self._eof():
            self._err("unexpected EOF")
        b = self.s[self.i]
        self.i += 1
        if b == 0x0A:
            self.line += 1
            self.col = 1
        else:
            self.col += 1
        return b

    def _err(self, msg: str) -> None:
        raise InputError(f"{msg} (line {self.line}, col {self.col})")

    def _consume_newline(self) -> None:
        b = self._peek()
        if b == 0x0A:
            self._advance()
            return
        if b == 0x0D:
            self._advance()
            if self._peek() != 0x0A:
                self._err("bare CR is not allowed (use LF or CRLF)")
            self._advance()
            self.line += 1
            self.col = 1
            return
        self._err("expected EOL")

    def skip_spaces(self) -> None:
        while (not self._eof()) and (self._peek() in (0x20, 0x09)):
            self._advance()

    def skip_ws(self) -> None:
        while not self._eof():
            b = self._peek()
            if b in (0x20, 0x09):
                self._advance()
            elif b in (0x0A, 0x0D):
                self._consume_newline()
            else:
                break

    def read_space(self) -> None:
        b = self._peek()
        if b not in (0x20, 0x09):
            self._err("expected SPACE/TAB")
        while (not self._eof()) and (self._peek() in (0x20, 0x09)):
            self._advance()

    def read_eoln(self) -> None:
        self._consume_newline()

    def read_eof(self) -> None:
        if not self._eof():
            self._err("expected EOF (extra data exists)")

    def read_token(self) -> str:
        b = self._peek()
        if b is None:
            self._err(f"unexpected EOF while reading token")
        if b in (0x20, 0x09):
            self._err(f"unexpected leading SPACE/TAB while reading token")
        if b in (0x0A, 0x0D):
            self._err(f"unexpected EOL while reading token")

        start = self.i
        while not self._eof():
            b = self._peek()
            if b in (0x20, 0x09, 0x0A, 0x0D):
                break
            self._advance()
        return self.s[start:self.i].decode("ascii")

    def read_int(self, lo=None, hi=None) -> int:
        t_str = self.read_token()
        t = t_str.encode("ascii")

        if t[:1] == b"-":
            body = t[1:]
            if len(body) == 0:
                self._err(f"int is not an integer")
        else:
            body = t

        if len(body) == 0 or (not all(48 <= c <= 57 for c in body)):
            self._err(f"int is not a base-10 integer")

        x = int(t_str)
        if lo is not None and x < lo:
            self._err(f"int out of range: {x} < {lo}")
        if hi is not None and x > hi:
            self._err(f"int out of range: {x} > {hi}")
        return x

    def read_string(self, min_len: int | None = None, max_len: int | None = None) -> str:

        s = self.read_token()

        if min_len is not None and len(s) < min_len:
            self._err(f"str too short: len={len(s)} < {min_len}")
        if max_len is not None and len(s) > max_len:
            self._err(f"str too long: len={len(s)} > {max_len}")

        return s

ins = StrictIn.from_stdin_ascii()

n = ins.read_int(2, 2 * 10**5)
ins.read_space()
m = ins.read_int(1, n - 1)
ins.read_eoln()

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

lrk = []
c = [0]*n
for _ in range(m):
    l = ins.read_int(1, n)
    ins.read_space()
    r = ins.read_int(l + 1, n)
    ins.read_space()
    k = ins.read_int(1, n)
    ins.read_eoln()

    for i in range(l-1, r):
        c[i] += 1
        assert c[i] <= 2

    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)
ins.read_eof()

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)