結果
問題 | No.1996 <>< |
ユーザー |
![]() |
提出日時 | 2022-07-01 22:43:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,475 ms / 2,000 ms |
コード長 | 1,560 bytes |
コンパイル時間 | 347 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 95,916 KB |
最終ジャッジ日時 | 2024-11-26 06:16:59 |
合計ジャッジ時間 | 17,709 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
class DualBIT():def __init__(self, init):if type(init) == int:self.n = init + 1self.X = [0] * self.nelse:self.n = len(init) + 1self.X = [0] + initfor i in range(1, self.n):if i + (i & -i) < self.n:self.X[i + (i & -i)] += self.X[i]def _add(self, i, x=1):i += 1while i < self.n:self.X[i] = (self.X[i] + x) % Pi += i & (-i)def add_range(self, l, r, x=1):self._add(l, x)self._add(r, -x)def getvalue(self, i):ret = 0i += 1while i != 0:ret = (ret + self.X[i]) % Pi -= i & (-i)return retdef disp(self):return [self.getvalue(i) for i in range(N)]P = 10 ** 9 + 7N, K = map(int, input().split())A = [int(a) for a in input().split()]S = [1 if s == "<" else -1 for s in input()]SA = sorted(set(A))IA = {a: i for i, a in enumerate(SA)}AA = [IA[a] for a in A]M = len(SA)bits = [DualBIT(N) for _ in range(K + 1)]bits[0].add_range(0, M, 1)ans = 0for i in range(N):a = AA[i]for j in range(1, K + 1)[::-1]:c = bits[j].getvalue(a)if j == K:ans += ccontinues = S[j]if s > 0:bits[j+1].add_range(a + 1, M, c)else:bits[j+1].add_range(0, a, c)s = S[0]if s > 0:bits[1].add_range(a + 1, M, 1)else:bits[1].add_range(0, a, 1)print(ans % P)