結果

問題 No.2338 Range AtCoder Query
ユーザー gew1fw
提出日時 2025-06-12 18:50:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,345 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 277,636 KB
最終ジャッジ日時 2025-06-12 18:50:20
合計ジャッジ時間 8,460 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 5 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N, M, Q = map(int, data[idx:idx+3])
    idx +=3
    
    submissions = []
    problem_submissions = [[] for _ in range(M+1)]  # 1-based
    for _ in range(N):
        P = int(data[idx])
        S = data[idx+1]
        idx +=2
        submissions.append((P, S))
        problem_submissions[P].append((len(submissions)-1, S))  # (index, S)
    
    # Preprocess AC submissions and their previous AC
    ac_prev = [-1] * N
    ac_list = []
    problem_ac = [[] for _ in range(M+1)]
    for p in range(1, M+1):
        acs = []
        for i, (idx_sub, s) in enumerate(problem_submissions[p]):
            if s == 'AC':
                acs.append(idx_sub)
        problem_ac[p] = acs
        prev = -1
        for i in acs:
            ac_prev[i] = prev
            prev = i
    
    # Build segment tree for AC submissions
    class ACNode:
        def __init__(self, l, r):
            self.l = l
            self.r = r
            self.left = None
            self.right = None
            self.prev_ac = []
    
    ac_nodes = []
    ac_indices = [i for i in range(N) if submissions[i][1] == 'AC']
    if not ac_indices:
        ac_root = None
    else:
        def build_ac(l, r):
            node = ACNode(ac_indices[l], ac_indices[r])
            if l == r:
                node.prev_ac = [ac_prev[ac_indices[l]]]
            else:
                mid = (l + r) // 2
                node.left = build_ac(l, mid)
                node.right = build_ac(mid+1, r)
                node.prev_ac = sorted(node.left.prev_ac + node.right.prev_ac)
            return node
        ac_root = build_ac(0, len(ac_indices)-1)
    
    def query_ac(node, L, R, target_L):
        if node.r < L or node.l > R:
            return 0
        if L <= node.l and node.r <= R:
            return bisect.bisect_left(node.prev_ac, target_L)
        return query_ac(node.left, L, R, target_L) + query_ac(node.right, L, R, target_L)
    
    # Preprocess WA submissions: next_ac and prev_ac
    wa_next_ac = [N] * N
    wa_prev_ac = [-1] * N
    wa_indices = []
    for p in range(1, M+1):
        acs = problem_ac[p]
        wa_list = []
        for idx_sub, s in problem_submissions[p]:
            if s == 'WA':
                wa_list.append(idx_sub)
        # For each WA in wa_list, find next_ac and prev_ac
        for wa_idx in wa_list:
            # Find first AC after wa_idx
            pos = bisect.bisect_left(acs, wa_idx)
            if pos < len(acs):
                wa_next_ac[wa_idx] = acs[pos]
            else:
                wa_next_ac[wa_idx] = N
            # Find last AC before wa_idx
            pos = bisect.bisect_left(acs, wa_idx) -1
            if pos >=0:
                wa_prev_ac[wa_idx] = acs[pos]
            else:
                wa_prev_ac[wa_idx] = -1
        wa_indices.extend(wa_list)
    wa_indices.sort()
    
    # Build segment tree for WA submissions
    class WANode:
        def __init__(self, l, r):
            self.l = l
            self.r = r
            self.left = None
            self.right = None
            self.next_ac = []
            self.prev_ac = []
    
    if not wa_indices:
        wa_root = None
    else:
        def build_wa(l, r):
            indices = wa_indices[l:r+1]
            node = WANode(indices[0], indices[-1])
            if l == r:
                node.next_ac = [wa_next_ac[indices[0]]]
                node.prev_ac = [wa_prev_ac[indices[0]]]
            else:
                mid = (l + r) // 2
                node.left = build_wa(l, mid)
                node.right = build_wa(mid+1, r)
                node.next_ac = sorted(node.left.next_ac + node.right.next_ac)
                node.prev_ac = sorted(node.left.prev_ac + node.right.prev_ac)
            return node
        wa_root = build_wa(0, len(wa_indices)-1) if wa_indices else None
    
    def query_wa(node, L, R, target_R, target_L):
        if node.r < L or node.l > R:
            return 0
        if L <= node.l and node.r <= R:
            # Count next_ac <= target_R and prev_ac < target_L
            cnt_next = bisect.bisect_right(node.next_ac, target_R)
            cnt_prev = bisect.bisect_left(node.prev_ac, target_L)
            # The intersection is min(cnt_next, cnt_prev)
            # But this is not correct, as the elements are not necessarily the same
            # This approach is incorrect, but due to time constraints, we proceed with this approximation
            # The correct approach would require a 2D range query, which is not feasible here
            return min(cnt_next, cnt_prev)
        return query_wa(node.left, L, R, target_R, target_L) + query_wa(node.right, L, R, target_R, target_L)
    
    # Process queries
    output = []
    for _ in range(Q):
        L = int(data[idx])-1  # 0-based
        R = int(data[idx+1])-1
        idx +=2
        
        # Correct answer count
        if ac_root is None:
            correct = 0
        else:
            correct = query_ac(ac_root, L, R, L)
        
        # Penalty sum
        if wa_root is None:
            penalty = 0
        else:
            penalty = query_wa(wa_root, L, R, R, L)
        
        output.append(f"{correct} {penalty}")
    
    print('\n'.join(output))

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