結果

問題 No.2338 Range AtCoder Query
ユーザー lam6er
提出日時 2025-03-31 17:52:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,662 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,828 KB
実行使用メモリ 78,572 KB
最終ジャッジ日時 2025-03-31 17:52:48
合計ジャッジ時間 9,393 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, M, Q = map(int, input[ptr:ptr+3])
    ptr += 3

    P = []
    S = []
    AC_positions = []

    submissions = defaultdict(list)  # key: problem p, value: list of (index in original array)
    ac_submissions = defaultdict(list)
    prefix_wa = defaultdict(list)    # prefix_wa[p] is the prefix sum array for WA counts

    for idx in range(N):
        p = int(input[ptr])-1  # convert to 0-based
        s = input[ptr+1]
        ptr +=2
        P.append(p)
        S.append(s)
        submissions[p].append(idx+1)  # indices are 1-based
        if s == 'AC':
            AC_positions.append(idx+1)
            ac_submissions[p].append(idx+1)
        # build prefix_wa
        current = submissions[p]
        plen = len(current)
        if plen == 1:
            prefix_wa[p] = [0]
        # add to prefix_wa[p]
        last = prefix_wa[p][-1]
        if s == 'WA':
            new_last = last + 1
        else:
            new_last = last
        prefix_wa[p].append(new_last)

    # Read queries
    queries = []
    for _ in range(Q):
        L = int(input[ptr])
        R = int(input[ptr+1])
        queries.append((L, R))
        ptr +=2

    # Process each query
    for L, R in queries:
        # Find AC submissions in [L, R]
        left = bisect.bisect_left(AC_positions, L)
        right = bisect.bisect_right(AC_positions, R)
        ac_in_query = AC_positions[left:right]

        # Group by p and find the earliest j for each p
        p_earliest = dict()
        for j in ac_in_query:
            p = P[j-1]  # j is 1-based, P is 0-based list
            if p not in p_earliest or j < p_earliest[p]:
                p_earliest[p] = j

        correct_count = len(p_earliest)
        penalty_sum = 0

        for p, j in p_earliest.items():
            # Get submissions for p
            sub_list = submissions.get(p, [])
            if not sub_list:
                continue  # not possible
            # Find WA submissions between L and j-1
            target_L = L
            target_R = j -1
            # find first index in sub_list >= target_L
            left_sub = bisect.bisect_left(sub_list, target_L)
            # find last index <= target_R
            right_sub = bisect.bisect_right(sub_list, target_R) -1
            if left_sub > right_sub:
                continue
            # calculate WA count
            pr_wa = prefix_wa[p]
            wa = pr_wa[right_sub +1] - pr_wa[left_sub]
            penalty_sum += wa

        print(correct_count, penalty_sum)

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