結果

問題 No.3269 Leq-K Partition
コンテスト
ユーザー navel_tos
提出日時 2026-01-27 01:45:51
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 1,659 ms / 6,000 ms
コード長 3,027 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 335 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 330,352 KB
最終ジャッジ日時 2026-01-27 01:46:25
合計ジャッジ時間 24,956 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#yukicoder3269 Leq-K Partition

#関数内実行
def main():
    #入力受取
    N: int = int(input())
    A: list[int] = [int(Ai) - 1 for Ai in input().split()]

    #平方分割
    sqN: int = min(N, int(N ** 0.5) + 1)

    #k := [1, sqN] は愚直に
    ans: list[str] = [''] * N
    C: list[int] = [-1] * N
    cnt: int = 0
    for k in range(1, sqN + 1):
        offset: int = cnt  #今回の分割開始点
        kind: int = 0  #現在の種類数
        for Ai in A:
            if C[Ai] != cnt:
                if kind == k:
                    cnt += 1
                    kind: int = 0
                C[Ai] = cnt
                kind += 1
        cnt += 1
        ans[k - 1] = str(cnt - offset)

    #k > sqN は尺取法で実行
    #B[b]: ブロックbの現在の 左端 << 32 | 右端
    #D[b]: ブロックbの現在の頻度分布(0 <= c < N), 種類数(c == N)
    B: list[int] = [0] * (sqN + 2)
    D: list[list[int]] = [[0] * (N + 1) for _ in range(sqN + 2)]

    #k == sqN + 1 に対して初期解を作成  区間[N, N) の存在は認める
    k: int = sqN + 1
    Rt: int = 0
    for b in range(sqN + 2):
        if Rt == N:
            B[b] = N << 32 | N
            continue
        Lt: int = Rt
        C: list[int] = D[b]
        while Rt < N:
            if C[A[Rt]] == 0:
                if C[N] == k:
                    break
                else:
                    C[N] += 1
            C[A[Rt]] += 1
            Rt += 1
        B[b] = Lt << 32 | Rt

    #現在の有効なブロック数を数え上げ
    for b_Rt in range(sqN + 2):
        if B[b_Rt] & 0xFFFFFFFF == N:
            b_Rt += 1
            break
    if k <= N:
        ans[k - 1] = str(b_Rt)
            
    #b_Rt == 1 になるまで、kを1加算する
    for k in range(sqN + 2, N + 1):
        if b_Rt == 1:
            ans[k - 1] = '1'
            continue
        b: int = 0
        while b < b_Rt:
            Lt, Rt = B[b] >> 32, B[b] & 0xFFFFFFFF
            C: list[int] = D[b]
            if b != 0:  #Ltを動かす
                prev_Rt: int = B[b - 1] & 0xFFFFFFFF
                while Lt < prev_Rt:
                    if Lt == Rt:
                        Lt = Rt = Lt + 1
                        continue
                    if C[A[Lt]] == 1:
                        C[N] -= 1
                    C[A[Lt]] -= 1
                    Lt += 1
            else:
                assert Lt == 0

            #Rtを動かす
            assert Lt <= Rt and C[N] < k
            while Rt < N:
                if C[A[Rt]] == 0:
                    if C[N] == k:
                        break
                    else:
                        C[N] += 1
                C[A[Rt]] += 1
                Rt += 1

            #更新後の結果を格納
            B[b] = Lt << 32 | Rt
            b += 1
            if Rt == N:
                b_Rt: int = b
                break
        ans[k - 1] = str(b_Rt)
            
    #答えを出力
    __import__('sys').stdout.write('\n'.join(ans))


main()
0