結果

問題 No.2338 Range AtCoder Query
ユーザー lam6er
提出日時 2025-04-16 15:48:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,557 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 81,612 KB
実行使用メモリ 228,592 KB
最終ジャッジ日時 2025-04-16 15:50:28
合計ジャッジ時間 45,218 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect
from collections import defaultdict

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

    P = []
    S = []
    for _ in range(N):
        p = int(input[ptr])
        s = input[ptr+1]
        ptr +=2
        P.append(p)
        S.append(s)
    
    # Preprocess next_ac for WA submissions
    problem_ac = defaultdict(list)
    for i in range(N):
        if S[i] == 'AC':
            problem_ac[P[i]].append(i+1)  # 1-based
    
    next_ac = [0]*(N+2)  # 1-based
    for i in range(1, N+1):
        if S[i-1] == 'WA':
            p = P[i-1]
            ac_list = problem_ac.get(p, [])
            idx = bisect.bisect_right(ac_list, i)
            if idx < len(ac_list):
                next_ac[i] = ac_list[idx]
            else:
                next_ac[i] = float('inf')
        else:
            next_ac[i] = float('inf')
    
    # Build segment tree for WA submissions' next_ac
    class SegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<=1
            self.tree = [[] for _ in range(2*self.size)]
            for i in range(self.n):
                if S[i] == 'WA':
                    self.tree[self.size + i] = [next_ac[i+1]]  # data is 0-based, next_ac is 1-based
                else:
                    self.tree[self.size + i] = []
            for i in range(self.size-1, 0, -1):
                self.tree[i] = sorted(self.tree[2*i] + self.tree[2*i+1])
        
        def query(self, l, r, R):
            res = 0
            l += self.size -1  # convert to 1-based in the tree
            r += self.size
            while l < r:
                if l %2 ==1:
                    res += bisect.bisect_right(self.tree[l], R)
                    l +=1
                if r %2 ==1:
                    r -=1
                    res += bisect.bisect_right(self.tree[r], R)
                l >>=1
                r >>=1
            return res
    
    # Prepare data for segment tree (WA submissions)
    data = [i+1 for i in range(N) if S[i] == 'WA']
    st = SegmentTree([(i+1) for i in range(N)])
    
    # Process AC submissions for correct count using BIT
    ac_indices = []
    for i in range(N):
        if S[i] == 'AC':
            ac_indices.append(i+1)  # 1-based
    
    # Build BIT for correct count
    class BIT:
        def __init__(self, size):
            self.size = size
            self.tree = [0]*(size+2)
        
        def add(self, idx, val):
            while idx <= self.size:
                self.tree[idx] += val
                idx += idx & -idx
        
        def query(self, idx):
            res =0
            while idx >0:
                res += self.tree[idx]
                idx -= idx & -idx
            return res
    
    bit = BIT(N)
    last_occurrence = {}
    for j in ac_indices:
        p = P[j-1]
        if p in last_occurrence:
            prev_j = last_occurrence[p]
            bit.add(prev_j, -1)
        bit.add(j, 1)
        last_occurrence[p] = j
    
    # Process queries
    output = []
    for _ in range(Q):
        L = int(input[ptr])
        R = int(input[ptr+1])
        ptr +=2
        # Correct count
        correct = bit.query(R) - bit.query(L-1)
        # Penalty count
        penalty = st.query(L, R, R)
        output.append(f"{correct} {penalty}")
    
    print('\n'.join(output))
    
if __name__ == '__main__':
    main()
0