結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー gew1fw
提出日時 2025-06-12 16:33:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,779 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,528 KB
実行使用メモリ 149,512 KB
最終ジャッジ日時 2025-06-12 16:33:39
合計ジャッジ時間 12,273 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff #

import bisect
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split('\n')
    ptr = 0

    n = int(data[ptr].strip())
    ptr += 1
    levels = list(map(int, data[ptr].strip().split()))
    ptr += 1
    t = int(data[ptr].strip())
    ptr += 1
    submissions = []
    for _ in range(t):
        if data[ptr].strip() == '':
            ptr += 1
            continue
        parts = data[ptr].strip().split()
        name = parts[0]
        p = parts[1]
        submissions.append((name, p))
        ptr += 1

    participants = {}  # name: (score, last_time, solved_problems)
    score_dict = defaultdict(list)  # score: sorted list of last_time
    max_score = sum(levels)
    freq = [0] * (max_score + 2)  # freq[s] is the count of participants with score s

    for idx, sub in enumerate(submissions, 1):
        name = sub[0]
        p = sub[1]
        if p != '?':
            # Process a problem submission
            problem_num = ord(p) - ord('A')
            if problem_num < 0 or problem_num >= n:
                continue  # invalid problem, skip
            L = levels[problem_num]
            if name not in participants:
                participants[name] = (0, 0, set())
            current_score, current_time, solved = participants[name]
            if problem_num in solved:
                continue  # already solved, no change
            solved.add(problem_num)
            new_score = current_score + L
            # Remove from old score's list
            old_score = current_score
            old_list = score_dict[old_score]
            pos = bisect.bisect_left(old_list, current_time)
            if pos < len(old_list) and old_list[pos] == current_time:
                old_list.pop(pos)
            freq[old_score] -= 1
            # Add to new score's list
            bisect.insort(score_dict[new_score], idx)
            freq[new_score] += 1
            # Update participant's data
            participants[name] = (new_score, idx, solved)
        else:
            # Process a query
            if name not in participants:
                print(1)
                continue
            current_score, current_time, _ = participants[name]
            # Compute count1: sum of freq for S' > current_score
            count1 = 0
            for s in range(current_score + 1, max_score + 1):
                count1 += freq[s]
            # Compute count2: number of participants with score == current_score and last_time < current_time
            lst = score_dict.get(current_score, [])
            count2 = bisect.bisect_left(lst, current_time)
            # Calculate rank
            rank = count1 + count2 + 1
            print(rank)
    return

if __name__ == "__main__":
    main()
0