結果

問題 No.2338 Range AtCoder Query
ユーザー gew1fw
提出日時 2025-06-12 14:44:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,655 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,260 KB
実行使用メモリ 78,720 KB
最終ジャッジ日時 2025-06-12 14:46:26
合計ジャッジ時間 9,767 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx +=1
    M = int(data[idx]); idx +=1
    Q = int(data[idx]); idx +=1
    
    # Preprocess for each problem p
    from collections import defaultdict
    problem_data = defaultdict(list)
    for i in range(N):
        p = int(data[idx]); idx +=1
        s = data[idx]; idx +=1
        problem_data[p].append( (i+1, s) )  # positions are 1-based

    queries = []
    for q_idx in range(Q):
        L = int(data[idx]); idx +=1
        R = int(data[idx]); idx +=1
        queries.append( (L, R) )

    # For each p, preprocess pos_list, is_ac_list, wa_prefix, ac_indices
    p_info = {}
    for p in problem_data:
        pos_list = []
        is_ac_list = []
        ac_indices = []
        for (pos, s) in problem_data[p]:
            pos_list.append(pos)
            is_ac_list.append(s == 'AC')
            if s == 'AC':
                ac_indices.append( len(pos_list)-1 )  # 0-based index

        # Compute wa_prefix
        wa_prefix = [0]
        count = 0
        for s in is_ac_list:
            if s == False:
                count +=1
            wa_prefix.append(count)
        
        p_info[p] = {
            'pos_list': pos_list,
            'is_ac_list': is_ac_list,
            'wa_prefix': wa_prefix,
            'ac_indices': ac_indices
        }

    # Process each query
    results = []
    for L, R in queries:
        correct = 0
        penalty = 0
        for p in p_info:
            data_p = p_info[p]
            pos_list = data_p['pos_list']
            is_ac_list = data_p['is_ac_list']
            wa_prefix = data_p['wa_prefix']
            ac_indices = data_p['ac_indices']

            # Find a: first index >= L
            a = bisect.bisect_left(pos_list, L)
            # Find b: last index <= R
            b = bisect.bisect_right(pos_list, R) - 1

            if a > b:
                continue

            # Check if any AC in a..b
            # Find the first AC in a..b
            idx_ac = bisect.bisect_left(ac_indices, a)
            if idx_ac < len(ac_indices) and ac_indices[idx_ac] <= b:
                j = ac_indices[idx_ac]
                if j < a or j > b:
                    continue
                penalty_p = wa_prefix[j+1] - wa_prefix[a]
                penalty += penalty_p
                correct +=1
            else:
                # No AC in this p's range
                continue

        results.append( (correct, penalty) )

    # Output the results
    for res in results:
        print(res[0], res[1])

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