結果
問題 |
No.449 ゆきこーだーの雨と雪 (4)
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:26:52 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,508 bytes |
コンパイル時間 | 448 ms |
コンパイル使用メモリ | 81,688 KB |
実行使用メモリ | 227,520 KB |
最終ジャッジ日時 | 2025-04-16 00:28:21 |
合計ジャッジ時間 | 13,677 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 WA * 35 |
ソースコード
import sys class FenwickTree: def __init__(self, size): self.n = size self.tree = [0] * (self.n + 2) # 1-based indexing def update(self, idx, delta): if idx == 0: return while idx <= self.n: self.tree[idx] += delta idx += idx & -idx def query(self, idx): res = 0 if idx <= 0: return 0 while idx > 0: res += self.tree[idx] idx -= idx & -idx return res class User: def __init__(self): self.score = 0 self.last_time = 0 self.solved_problems = set() def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 L = list(map(int, input[ptr:ptr+N])) ptr += N sum_L = sum(L) max_score = sum_L T = int(input[ptr]) ptr += 1 max_time = 10**5 + 2 fenwick_trees = [FenwickTree(max_time) for _ in range(max_score + 1)] freq = [0] * (max_score + 1) user_map = {} output = [] for timestamp in range(1, T + 1): Name_i = input[ptr] P_i = input[ptr + 1] ptr += 2 if P_i != '?': problem_char = P_i problem_index = ord(problem_char) - ord('A') level = L[problem_index] if Name_i not in user_map: user = User() user_map[Name_i] = user else: user = user_map[Name_i] if problem_char not in user.solved_problems: old_s = user.score old_t = user.last_time if old_t != 0: ft = fenwick_trees[old_s] ft.update(old_t, -1) freq[old_s] -= 1 new_s = old_s + level new_t = timestamp ft = fenwick_trees[new_s] ft.update(new_t, 1) freq[new_s] += 1 user.score = new_s user.last_time = new_t user.solved_problems.add(problem_char) else: user = user_map[Name_i] s = user.score t = user.last_time sum_higher = 0 for j in range(s + 1, max_score + 1): sum_higher += freq[j] ft = fenwick_trees[s] count = ft.query(t - 1) rank = sum_higher + count + 1 output.append(str(rank)) print('\n'.join(output)) if __name__ == '__main__': main()