結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー lam6er
提出日時 2025-04-16 16:44:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,508 bytes
コンパイル時間 1,253 ms
コンパイル使用メモリ 81,656 KB
実行使用メモリ 227,784 KB
最終ジャッジ日時 2025-04-16 16:46:01
合計ジャッジ時間 12,496 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0