結果

問題 No.992 最長増加部分列の数え上げ
ユーザー lam6er
提出日時 2025-03-31 17:56:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 579 ms / 2,000 ms
コード長 3,444 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 157,156 KB
最終ジャッジ日時 2025-03-31 17:57:20
合計ジャッジ時間 19,740 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import bisect
MOD = 10**9 + 7
class SegmentTree:
    def __init__(self, data_size):
        self.n = data_size
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.max_len = [0] * (2 * self.size)
        self.sum_cnt = [0] * (2 * self.size)
    
    def update(self, pos, new_len, new_cnt):
        pos += self.size
        if self.max_len[pos] < new_len:
            self.max_len[pos] = new_len
            self.sum_cnt[pos] = new_cnt % MOD
        elif self.max_len[pos] == new_len:
            self.sum_cnt[pos] = (self.sum_cnt[pos] + new_cnt) % MOD
        else:
            return
        pos >>= 1
        while pos >= 1:
            left = pos << 1
            right = left + 1
            left_max = self.max_len[left]
            left_cnt = self.sum_cnt[left]
            right_max = self.max_len[right]
            right_cnt = self.sum_cnt[right]
            if left_max > right_max:
                combined_max = left_max
                combined_cnt = left_cnt
            elif right_max > left_max:
                combined_max = right_max
                combined_cnt = right_cnt
            else:
                combined_max = left_max
                combined_cnt = (left_cnt + right_cnt) % MOD
            if self.max_len[pos] == combined_max and self.sum_cnt[pos] == combined_cnt:
                break
            self.max_len[pos] = combined_max
            self.sum_cnt[pos] = combined_cnt
            pos >>= 1
    
    def query(self, l, r):
        res_max = 0
        res_cnt = 0
        l += self.size
        r += self.size
        while l <= r:
            if l % 2 == 1:
                current_max = self.max_len[l]
                current_cnt = self.sum_cnt[l]
                if current_max > res_max:
                    res_max = current_max
                    res_cnt = current_cnt
                elif current_max == res_max:
                    res_cnt = (res_cnt + current_cnt) % MOD
                l += 1
            if r % 2 == 0:
                current_max = self.max_len[r]
                current_cnt = self.sum_cnt[r]
                if current_max > res_max:
                    res_max = current_max
                    res_cnt = current_cnt
                elif current_max == res_max:
                    res_cnt = (res_cnt + current_cnt) % MOD
                r -= 1
            l >>= 1
            r >>= 1
        return res_max, res_cnt
def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    sorted_unique = sorted(set(A))
    m = len(sorted_unique)
    compressed = []
    for x in A:
        k = bisect.bisect_left(sorted_unique, x)
        compressed.append(k)
    if m == 0:
        print(0)
        return
    tree = SegmentTree(m)
    global_max = 0
    global_sum = 0
    for k in compressed:
        if k == 0:
            max_prev, sum_prev = 0, 0
        else:
            max_prev, sum_prev = tree.query(0, k-1)
        if max_prev == 0 and sum_prev == 0:
            len_i = 1
            cnt_i = 1
        else:
            len_i = max_prev + 1
            cnt_i = sum_prev
        tree.update(k, len_i, cnt_i)
        if len_i > global_max:
            global_max = len_i
            global_sum = cnt_i
        elif len_i == global_max:
            global_sum = (global_sum + cnt_i) % MOD
    print(global_sum % MOD)
if __name__ == "__main__":
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0