結果

問題 No.2338 Range AtCoder Query
ユーザー lam6er
提出日時 2025-04-16 15:49:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,603 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 81,880 KB
実行使用メモリ 77,564 KB
最終ジャッジ日時 2025-04-16 15:51:28
合計ジャッジ時間 8,475 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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 = int(input[ptr])
    ptr +=1
    M = int(input[ptr])
    ptr +=1
    Q = int(input[ptr])
    ptr +=1

    ac_lists = defaultdict(list)
    wa_lists = defaultdict(list)
    global_ac = []

    for i in range(1, N+1):
        p = int(input[ptr])
        ptr +=1
        s = input[ptr]
        ptr +=1
        if s == 'AC':
            ac_lists[p].append(i)
            global_ac.append( (i, p) )
        else:
            wa_lists[p].append(i)

    # Sort global_ac by position
    global_ac.sort(key=lambda x: x[0])

    for _ in range(Q):
        L = int(input[ptr])
        ptr +=1
        R = int(input[ptr])
        ptr +=1

        # Find the range in global_ac where pos is between L and R
        left = bisect.bisect_left(global_ac, (L, 0))
        right = bisect.bisect_right(global_ac, (R, M+1))

        ac_submissions = global_ac[left:right]

        # Group by problem and find the earliest AC
        groups = {}
        for pos, p in ac_submissions:
            if p not in groups or pos < groups[p]:
                groups[p] = pos

        correct = len(groups)
        penalty = 0

        for p in groups:
            x = groups[p]
            wa_positions = wa_lists[p]
            # Find number of WAs >= L and <= x-1
            left_wa = bisect.bisect_left(wa_positions, L)
            right_wa = bisect.bisect_right(wa_positions, x-1)
            penalty += (right_wa - left_wa)

        print(correct, penalty)

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