#995662 (PyPy3) No.992 最長増加部分列の数え上げ

• 問題: No.992 最長増加部分列の数え上げ
• ユーザー: norioc
• 提出日時: 2024-07-17 23:25:15
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,056 ms / 2,000 ms
• コード長: 1,766 bytes
• コンパイル時間: 186 ms
• コンパイル使用メモリ: 82,160 KB
• 実行使用メモリ: 271,476 KB
• 最終ジャッジ日時: 2024-07-17 23:25:41
• 合計ジャッジ時間: 25,834 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 42

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
from bisect import bisect_left
from collections import defaultdict
def compress(a: list) -> list:
    d = {v: i for i, v in enumerate(sorted(set(a)))}
    return [d[v] for v in a]
class FenwickTree:
    def __init__(self, n):
        self.data = [0] * (n+10)
        self.n = (n+10)
    def add(self, p, x):
        assert 0 <= p < self.n
        p += 1
        while p < len(self.data):
            self.data[p] += x
            p += p & -p
    def sum(self, p):
        """区間 [0, p] の和"""
        assert 0 <= p < self.n
        p += 1
        s = 0
        while p > 0:
            s += self.data[p]
            p -= p & -p
        return s
    def rangesum(self, l, r):
        """区間 [l, r] の和"""
        assert 0 <= l <= r < self.n
        s = self.sum(r)
        if l > 0:
            s -= self.sum(l-1)
        return s
# LIS のアルゴリズム
# 各要素のランクを返す
def lis_ranks(a: list) -> list:
    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
MOD = 10 ** 9 + 7
INF = 1 << 60
N = int(input())
A = compress(list(map(int, input().split())))
ranks = lis_ranks(A)
max_rank = max(ranks)
d = defaultdict(list)
for i in range(N):
    d[ranks[i]].append(i)
dp = [0] * N
for p in d[max_rank]:
    dp[p] = 1
for rank in reversed(range(max_rank)):
    pp = [0] * N
    dp, pp = pp, dp
    ft = FenwickTree(N)
    inds = d[rank+1].copy()
    for p in reversed(d[rank]):
        while inds and p < inds[-1]:
            k = inds[-1]
            ft.add(A[k], pp[k])
            inds.pop()
        dp[p] = ft.rangesum(A[p]+1, N) % MOD
ans = sum(dp) % MOD
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX