結果

問題 No.2338 Range AtCoder Query
ユーザー gew1fw
提出日時 2025-06-12 18:51:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,748 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 272,632 KB
最終ジャッジ日時 2025-06-12 18:51:19
合計ジャッジ時間 9,066 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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])
    M = int(data[idx+1])
    Q = int(data[idx+2])
    idx +=3
    
    from collections import defaultdict
    problems = defaultdict(list)
    ac_positions = defaultdict(list)
    submissions = []
    
    for _ in range(N):
        p = int(data[idx])-1  # 0-based
        s = data[idx+1]
        idx +=2
        submissions.append( (p, s) )
        problems[p].append(len(submissions)-1)  # 0-based
        if s == 'AC':
            ac_positions[p].append(len(submissions)-1)
    
    # Precompute prefix_wa for each problem
    prefix_wa = defaultdict(list)
    for p in problems:
        wa = 0
        prefix = []
        for idx_sub in problems[p]:
            s = submissions[idx_sub][1]
            if s == 'WA':
                wa +=1
            prefix.append(wa)
        prefix_wa[p] = prefix
    
    # Process queries
    for _ in range(Q):
        L = int(data[idx])-1  # 0-based
        R = int(data[idx+1])-1
        idx +=2
        
        # Collect unique problems in [L, R]
        unique_p = set()
        for i in range(L, R+1):
            p, _ = submissions[i]
            unique_p.add(p)
        
        count = 0
        penalty = 0
        
        for p in unique_p:
            # Check if there are any AC in p's submissions in [L, R]
            ac_list = ac_positions[p]
            if not ac_list:
                continue
            
            # Find the first AC >= L and <= R
            left = 0
            right = len(ac_list)-1
            first_ac_idx = -1
            while left <= right:
                mid = (left + right) //2
                ac_sub = ac_list[mid]
                if ac_sub >= L:
                    right = mid -1
                    first_ac_idx = mid
                else:
                    left = mid +1
            
            if first_ac_idx == -1:
                # All AC are < L
                continue
            first_ac_sub = ac_list[first_ac_idx]
            if first_ac_sub > R:
                continue
            
            # Found an AC in [L, R]
            count +=1
            
            # Now find WA's in S_p >= L and < first_ac_sub
            S_p = problems[p]
            a = bisect.bisect_left(S_p, L)
            b = bisect.bisect_left(S_p, first_ac_sub) -1
            if a > b:
                continue
            
            # Get the WA count
            prefix = prefix_wa[p]
            if a ==0:
                sum_wa = prefix[b]
            else:
                sum_wa = prefix[b] - prefix[a-1]
            penalty += sum_wa
        
        print(count, penalty)

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