結果
問題 |
No.1996 <><
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:27:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 698 ms / 2,000 ms |
コード長 | 2,027 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 82,420 KB |
実行使用メモリ | 114,552 KB |
最終ジャッジ日時 | 2025-03-20 20:29:10 |
合計ジャッジ時間 | 9,599 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
import bisect MOD = 10**9 + 7 class FenwickTree: def __init__(self, size): self.size = size self.tree = [0] * (self.size + 2) # 1-based indexing def update(self, idx, value): while idx <= self.size: self.tree[idx] = (self.tree[idx] + value) % MOD idx += idx & -idx def query(self, idx): res = 0 while idx > 0: res = (res + self.tree[idx]) % MOD idx -= idx & -idx return res def main(): import sys input = sys.stdin.read data = input().split() ptr = 0 N = int(data[ptr]) ptr +=1 K = int(data[ptr]) ptr +=1 A = list(map(int, data[ptr:ptr+N])) ptr += N s = data[ptr] ptr +=1 # Coordinate compression for ascending order sorted_asc = sorted(A) unique_asc = [] seen = set() for num in sorted_asc: if num not in seen: seen.add(num) unique_asc.append(num) max_rank = len(unique_asc) x_asc = [] for num in A: idx = bisect.bisect_left(unique_asc, num) x_asc.append(idx + 1) # 1-based index # Initialize DP dp = [[0] * (N + 2) for _ in range(K + 2)] # dp[k][j] for 1-based j for j in range(1, N+1): dp[0][j] = 1 for k in range(K): sign = s[k] ft = FenwickTree(max_rank) next_dp = [0] * (N + 2) for j in range(1, N+1): current_x = x_asc[j-1] # j is 1-based, A is 0-based if sign == '<': sum_val = ft.query(current_x -1) else: sum_total = ft.query(max_rank) sum_less_eq = ft.query(current_x) sum_val = (sum_total - sum_less_eq) % MOD next_dp[j] = sum_val % MOD # Update Fenwick Tree with dp[k][j] ft.update(current_x, dp[k][j]) dp[k+1] = next_dp total = 0 for j in range(1, N+1): total = (total + dp[K][j]) % MOD print(total % MOD) if __name__ == '__main__': main()