結果
問題 | No.1996 <>< |
ユーザー | tamato |
提出日時 | 2022-07-01 21:46:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 659 ms / 2,000 ms |
コード長 | 1,682 bytes |
コンパイル時間 | 235 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 81,536 KB |
最終ジャッジ日時 | 2024-05-04 16:06:50 |
合計ジャッジ時間 | 10,091 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
52,352 KB |
testcase_01 | AC | 41 ms
52,480 KB |
testcase_02 | AC | 41 ms
52,480 KB |
testcase_03 | AC | 51 ms
59,904 KB |
testcase_04 | AC | 44 ms
52,480 KB |
testcase_05 | AC | 46 ms
52,480 KB |
testcase_06 | AC | 39 ms
52,224 KB |
testcase_07 | AC | 40 ms
52,352 KB |
testcase_08 | AC | 55 ms
67,456 KB |
testcase_09 | AC | 48 ms
59,520 KB |
testcase_10 | AC | 59 ms
65,408 KB |
testcase_11 | AC | 362 ms
78,212 KB |
testcase_12 | AC | 637 ms
80,504 KB |
testcase_13 | AC | 658 ms
80,896 KB |
testcase_14 | AC | 659 ms
81,536 KB |
testcase_15 | AC | 574 ms
80,256 KB |
testcase_16 | AC | 507 ms
79,872 KB |
testcase_17 | AC | 603 ms
80,128 KB |
testcase_18 | AC | 375 ms
78,588 KB |
testcase_19 | AC | 434 ms
79,180 KB |
testcase_20 | AC | 410 ms
79,716 KB |
testcase_21 | AC | 511 ms
79,616 KB |
testcase_22 | AC | 598 ms
80,436 KB |
testcase_23 | AC | 84 ms
75,776 KB |
testcase_24 | AC | 375 ms
78,720 KB |
testcase_25 | AC | 217 ms
76,544 KB |
testcase_26 | AC | 319 ms
77,936 KB |
testcase_27 | AC | 118 ms
76,288 KB |
testcase_28 | AC | 54 ms
62,848 KB |
testcase_29 | AC | 210 ms
77,056 KB |
testcase_30 | AC | 67 ms
75,264 KB |
testcase_31 | AC | 132 ms
76,288 KB |
testcase_32 | AC | 60 ms
71,040 KB |
ソースコード
mod = 1000000007 def main(): import sys input = sys.stdin.readline class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1) def sum(self, i): s = 0 while i > 0: s += self.tree[i] s %= mod i -= i & -i return s def add(self, i, x): while i <= self.size: self.tree[i] += x self.tree[i] %= mod i += i & -i def lower_bound(self, w): if w <= 0: return 0 x = 0 k = 1 << (self.size.bit_length() - 1) while k: if x + k <= self.size and self.tree[x + k] < w: w -= self.tree[x + k] x += k k >>= 1 return x + 1 N, K = map(int, input().split()) A = list(map(int, input().split())) S = input().rstrip('\n') AI_inc = [(a, i+1) for i, a in enumerate(A)] AI_dec = [(a, i+1) for i, a in enumerate(A)] AI_inc.sort(key=lambda x: x[1], reverse=True) AI_inc.sort(key=lambda x: x[0]) AI_dec.sort(key=lambda x: x[1], reverse=True) AI_dec.sort(key=lambda x: x[0], reverse=True) dp = [1] * (N+1) for i, s in enumerate(S): if s == "<": AI = AI_inc else: AI = AI_dec dp_new = [0] * (N+1) bit = Bit(N) for a, i in AI: dp_new[i] = bit.sum(i) bit.add(i, dp[i]) dp = dp_new ans = 0 for x in dp: ans = (ans + x) % mod print(ans) if __name__ == '__main__': main()