結果

問題 No.992 最長増加部分列の数え上げ
ユーザー lam6er
提出日時 2025-03-20 20:52:44
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,760 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 849,204 KB
最終ジャッジ日時 2025-03-20 20:53:02
合計ジャッジ時間 9,328 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 MLE * 4 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

MOD = 10**9 + 7

n = int(input())
A = list(map(int, input().split()))

# Coordinate compression
unique_A = sorted(A)
compressed = {v: i for i, v in enumerate(sorted(set(A)))}
A_compressed = [compressed[x] for x in A]
m = len(compressed)

# Compute len[i] which is the length of LIS ending at i
L = []
len_i = []
for x in A:
    pos = bisect.bisect_left(L, x)
    if pos == len(L):
        L.append(x)
    else:
        L[pos] = x
    len_i.append(pos + 1)  # len_i is 1-based

max_len = max(len_i)

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # +2 to avoid index issues
    
    def update(self, idx, value):
        idx += 1  # convert to 1-based index
        while idx <= self.n + 1:
            self.tree[idx] = (self.tree[idx] + value) % MOD
            idx += idx & -idx
    
    def query(self, idx):
        idx += 1  # convert to 1-based index
        res = 0
        while idx > 0:
            res = (res + self.tree[idx]) % MOD
            idx -= idx & -idx
        return res

# Initialize Fenwick Trees for each possible layer
fenwick_trees = [None] * (max_len + 2)  # layers start from 1

answer = 0
for i in range(n):
    current_len = len_i[i]
    current_a = A_compressed[i]
    
    if current_len == 1:
        cnt = 1
    else:
        prev_layer = current_len - 1
        if fenwick_trees[prev_layer] is None:
            cnt = 0
        else:
            cnt = fenwick_trees[prev_layer].query(current_a - 1)
    
    if fenwick_trees[current_len] is None:
        fenwick_trees[current_len] = FenwickTree(m)
    fenwick_trees[current_len].update(current_a, cnt)
    
    if current_len == max_len:
        answer = (answer + cnt) % MOD

print(answer % MOD)
0