結果

問題 No.1804 Intersection of LIS
ユーザー lam6er
提出日時 2025-03-20 19:01:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 747 ms / 2,000 ms
コード長 2,989 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 200,860 KB
最終ジャッジ日時 2025-03-20 19:02:59
合計ジャッジ時間 17,038 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

class FenwickTreeMax:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based indexing
    
    def update(self, idx, value):
        while idx <= self.n:
            if self.tree[idx] < value:
                self.tree[idx] = value
            else:
                break
            idx += idx & -idx
    
    def query(self, idx):
        res = 0
        while idx > 0:
            if self.tree[idx] > res:
                res = self.tree[idx]
            idx -= idx & -idx
        return res

class SegmentTreeMax:
    def __init__(self, size):
        self.n = 1
        while self.n < size:
            self.n <<= 1
        self.size = self.n
        self.tree = [0] * (2 * self.n)
    
    def update(self, idx, value):
        idx += self.n - 1  # convert to 0-based leaf node in a 1-based tree array
        if self.tree[idx] >= value:
            return
        self.tree[idx] = value
        while idx > 1:
            idx >>= 1
            new_val = max(self.tree[2*idx], self.tree[2*idx+1])
            if self.tree[idx] == new_val:
                break
            self.tree[idx] = new_val
    
    def query_range(self, l, r):
        res = 0
        l += self.n - 1
        r += self.n - 1
        while l <= r:
            if l % 2 == 1:
                res = max(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = max(res, self.tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    P = list(map(int, input[1:N+1]))
    
    # Compute lis_end
    fenwick = FenwickTreeMax(N)
    lis_end = []
    for x in P:
        max_prev = fenwick.query(x-1)
        current = max_prev + 1
        lis_end.append(current)
        current_val = fenwick.query(x)
        if current > current_val:
            fenwick.update(x, current)
    
    L = max(lis_end)
    
    # Compute lis_start
    st = SegmentTreeMax(N)
    lis_start = [0] * N
    for i in range(N-1, -1, -1):
        x = P[i]
        if x < N:
            current_max = st.query_range(x + 1, N)
        else:
            current_max = 0
        lis_start[i] = current_max + 1 if current_max != 0 else 1
        current_val = st.query_range(x, x)
        if lis_start[i] > current_val:
            st.update(x, lis_start[i])
    
    # Collect groups
    groups = defaultdict(list)
    for i in range(N):
        if lis_end[i] + lis_start[i] - 1 == L:
            k = lis_end[i]
            groups[k].append(i)
    
    # Check groups and collect answer
    answer = []
    for k in groups:
        if len(groups[k]) == 1:
            i = groups[k][0]
            answer.append( (i, P[i]) )
    
    answer.sort()
    print(len(answer))
    if answer:
        print(' '.join(map(str, [x[1] for x in answer])))
    else:
        print()

if __name__ == '__main__':
    main()
0