#775130 (PyPy3) No.1996 <><

• 問題: No.1996 <><
• ユーザー: 👑 SPD_9X2
• 提出日時: 2022-07-01 22:05:26
• 言語: PyPy3 (7.3.15)
• 結果: TLE
• 実行時間: -
• コード長: 2,086 bytes
• コンパイル時間: 470 ms
• コンパイル使用メモリ: 82,228 KB
• 実行使用メモリ: 115,012 KB
• 最終ジャッジ日時: 2024-11-26 05:15:55
• 合計ジャッジ時間: 32,862 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
sample	AC * 4
other	AC * 21 TLE * 8

ソースコード

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
"""
dp[i][j] = i番目までで、j個の場合の数
dp[i未満][j-1] から推移できる
ただし、A[?] < A[i] or A[?] > A[i] の時だけ
K個の セグ木に載せれば解ける
"""
from sys import stdin
mod = 10**9+7
class RangeBIT:
    def __init__(self,N,indexed): #0-indexed or 1-indexed 指定可能
        self.bit1 = [0] * (N+2)
        self.bit2 = [0] * (N+2)
        self.mode = indexed
    def bitadd(self,a,w,bit): #aにwを加える(1-origin)
 
        x = a
        while x <= (len(bit)-1):
            bit[x] += w
            bit[x] %= mod
            x += x & (-1 * x)
 
    def bitsum(self,a,bit): #ind 1～aまでの和を求める
 
        ret = 0
        x = a
        while x > 0:
            ret += bit[x]
            x -= x & (-1 * x)
        return ret % mod
    
    def add(self,l,r,w): #半開区間[l,r)にwを加える
        l = l + (1-self.mode)
        r = r + (1-self.mode)
        self.bitadd(l,-1*w*l,self.bit1)
        self.bitadd(r,w*r,self.bit1)
        self.bitadd(l,w,self.bit2)
        self.bitadd(r,-1*w,self.bit2)
    def sum(self,l,r): #半開区間[l,r)の区間和
        l = l + (1-self.mode)
        r = r + (1-self.mode)
        ret =  self.bitsum(r,self.bit1) + r * self.bitsum(r,self.bit2)
        ret -= self.bitsum(l,self.bit1) + l * self.bitsum(l,self.bit2)
        return ret
N,K = map(int,stdin.readline().split())
A = list(map(int,stdin.readline().split()))
s = list(stdin.readline()[:-1])
adic = {}
alis = []
for i in A:
    if i not in adic:
        adic[i] = 0
        alis.append(i)
alis.sort()
for i in range(len(alis)):
    adic[alis[i]] = i
A = [ adic[i] for i in A ]
XXX = len(adic) + 2
bit = [RangeBIT(XXX,0) for i in range(K+1)]
for i in range(N):
    for j in range(K,0,-1):
        if s[j-1] == "<":
            now = bit[j-1].sum(0,A[i])
            bit[j].add(A[i],A[i]+1, now % mod )
        else:
            now = bit[j-1].sum(A[i]+1,XXX)
            bit[j].add(A[i],A[i]+1, now % mod )
    bit[0].add(A[i],A[i]+1,1)
print (bit[K].sum(0,XXX) % mod)
            
        
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX