結果
問題 |
No.1996 <><
|
ユーザー |
|
提出日時 | 2025-07-05 01:47:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,040 ms / 2,000 ms |
コード長 | 2,115 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 82,044 KB |
実行使用メモリ | 94,796 KB |
最終ジャッジ日時 | 2025-07-05 01:47:40 |
合計ジャッジ時間 | 13,385 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
## https://yukicoder.me/problems/no/1996 MOD = 10 ** 9 + 7 class BinaryIndexTree: """ フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス """ def __init__(self, size): self.size = size self.array = [0] * (size + 1) def add(self, x, a): index = x while index <= self.size: self.array[index] += a self.array[index] %= MOD index += index & (-index) def sum(self, x): index = x ans = 0 while index > 0: ans += self.array[index] ans %= MOD index -= index & (-index) return ans def least_upper_bound(self, value): if self.sum(self.size) < value: return -1 elif value <= 0: return 0 m = 1 while m < self.size: m *= 2 k = 0 k_sum = 0 while m > 0: k0 = k + m if k0 < self.size: if k_sum + self.array[k0] < value: k_sum += self.array[k0] k += m m //= 2 if k < self.size: return k + 1 else: return -1 def main(): N, K = map(int, input().split()) A = list(map(int, input().split())) S = input() # 座標圧縮 a_list = list(set(A)) a_list.sort() a_map = {} for i, a in enumerate(a_list): a_map[a] = i + 1 a_max = len(a_list) dp_bits = [BinaryIndexTree(a_max) for _ in range(K + 1)] for a in A: a_ = a_map[a] for k in reversed(range(K + 1)): if k == 0: dp_bits[k].add(a_, 1) else: if S[k - 1] == "<": x = dp_bits[k - 1].sum(a_ - 1) dp_bits[k].add(a_, x) else: x = dp_bits[k - 1].sum(dp_bits[k - 1].size) - dp_bits[k - 1].sum(a_) x %= MOD dp_bits[k].add(a_, x) print(dp_bits[-1].sum(dp_bits[-1].size)) if __name__ == "__main__": main()