結果

問題 No.1804 Intersection of LIS
ユーザー norioc
提出日時 2024-07-19 03:02:02
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,657 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 65,536 KB
最終ジャッジ日時 2024-07-19 03:02:18
合計ジャッジ時間 4,756 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, Counter
from bisect import bisect_left
from atcoder.segtree import SegTree


def lis_ranks(a: list) -> list:
    """LIS のランクを返す"""
    n = len(a)
    ranks = [0] * n  # ranks[i] : A[i] が LIS の何番目か
    dp = [INF] * n
    for i in range(n):
        ranks[i] = bisect_left(dp, a[i])
        dp[ranks[i]] = a[i]

    return ranks


def lis_candidates(a: list[int], ranks: list[int]) -> list[int]:
    """LIS の構成要素となりうる要素のインデックスを返す"""
    n = len(a)
    max_rank = max(ranks)

    d = defaultdict(set)  # key=ランク val=そのランクのインデックス集合
    res = []
    for i in range(n):
        d[ranks[i]].add(i)
        if ranks[i] == max_rank:
            res.append(i)

    segt = SegTree(max, 0, n+1)
    for rank in reversed(range(max_rank)):  # 大きい順にみていく
        for i in d[rank+1]:
            segt.set(i, a[i])

        for i in list(d[rank]):
            x = segt.prod(i+1, n)  # i より右側に a[i] より大きい値が存在するか
            if a[i] < x:
                res.append(i)
            else:
                d[rank].remove(i)  # LIS の要素ではないので削除

        # 戻す
        for i in d[rank+1]:
            segt.set(i, 0)

    return sorted([i for i in res])


INF = 1 << 60
N = int(input())
A = list(map(int, input().split()))
ranks = lis_ranks(A)
inds = lis_candidates(A, ranks)

freq = Counter()
for i in inds:
    freq[ranks[i]] += 1

ans = []
for i in inds:
    if freq[ranks[i]] == 1:  # 唯一のランクか？
        ans.append(A[i])

print(len(ans))
print(*ans)
0