結果

問題 No.2338 Range AtCoder Query
ユーザー lam6er
提出日時 2025-04-15 22:02:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,910 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 81,676 KB
実行使用メモリ 79,656 KB
最終ジャッジ日時 2025-04-15 22:04:13
合計ジャッジ時間 9,129 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 4 WA * 6 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #

import bisect
from collections import defaultdict

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
    
    submissions = []
    for _ in range(N):
        P = int(data[idx])
        S = data[idx+1]
        submissions.append((P, S))
        idx +=2
    
    # Preprocess AC positions for each problem
    ac_positions = defaultdict(list)
    wa_submissions = []  # list of (pos, p)
    for i in range(N):
        pos = i + 1  # 1-based
        p, s = submissions[i]
        if s == 'AC':
            ac_positions[p].append(pos)
        else:
            wa_submissions.append((pos, p))
    
    # Process AC submissions for next_p and build ac_list
    ac_list = []  # list of (pos, next_p)
    for p in ac_positions:
        positions = sorted(ac_positions[p])
        for i in range(len(positions)):
            pos = positions[i]
            if i < len(positions) - 1:
                next_p = positions[i+1]
            else:
                next_p = float('inf')
            ac_list.append((pos, next_p))
    ac_list.sort()
    ac_positions_sorted = [pos for pos, _ in ac_list]
    ac_next_p_sorted = [next_p for _, next_p in ac_list]
    
    # Build AC segment tree
    class ACSegmentTree:
        def __init__(self, data_positions, data_next_p):
            self.n = len(data_positions)
            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):
                self.tree[self.size + i] = [data_next_p[i]]
            for i in range(self.size-1, 0, -1):
                left = self.tree[2*i]
                right = self.tree[2*i+1]
                merged = []
                l = r =0
                while l < len(left) and r < len(right):
                    if left[l] < right[r]:
                        merged.append(left[l])
                        l +=1
                    else:
                        merged.append(right[r])
                        r +=1
                merged.extend(left[l:])
                merged.extend(right[r:])
                self.tree[i] = merged
        
        def query(self, L, R, R_max):
            left_idx = bisect.bisect_left(ac_positions_sorted, L)
            right_idx = bisect.bisect_right(ac_positions_sorted, R) -1
            if left_idx > right_idx:
                return 0
            return self._query(1, 0, self.size-1, left_idx, right_idx, R_max)
        
        def _query(self, node, node_L, node_R, q_L, q_R, R_max):
            if node_R < q_L or node_L > q_R:
                return 0
            if q_L <= node_L and node_R <= q_R:
                cnt = len(self.tree[node]) - bisect.bisect_right(self.tree[node], R_max)
                return cnt
            mid = (node_L + node_R) //2
            return self._query(2*node, node_L, mid, q_L, q_R, R_max) + self._query(2*node+1, mid+1, node_R, q_L, q_R, R_max)
    
    ac_segment_tree = ACSegmentTree(ac_positions_sorted, ac_next_p_sorted)
    
    # Process WA submissions for next_ac
    wa_data = []  # list of (pos, next_ac)
    for pos, p in wa_submissions:
        if p not in ac_positions or not ac_positions[p]:
            next_ac = float('inf')
        else:
            idx_p = bisect.bisect_right(ac_positions[p], pos)
            if idx_p < len(ac_positions[p]):
                next_ac = ac_positions[p][idx_p]
            else:
                next_ac = float('inf')
        wa_data.append((pos, next_ac))
    wa_data.sort()
    wa_positions = [pos for pos, _ in wa_data]
    wa_next_ac = [next_ac for _, next_ac in wa_data]
    
    # Build WA segment tree
    class WASegmentTree:
        def __init__(self, data_positions, data_next_ac):
            self.n = len(data_positions)
            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):
                self.tree[self.size + i] = [data_next_ac[i]]
            for i in range(self.size-1, 0, -1):
                left = self.tree[2*i]
                right = self.tree[2*i+1]
                merged = []
                l = r =0
                while l < len(left) and r < len(right):
                    if left[l] < right[r]:
                        merged.append(left[l])
                        l +=1
                    else:
                        merged.append(right[r])
                        r +=1
                merged.extend(left[l:])
                merged.extend(right[r:])
                self.tree[i] = merged
        
        def query(self, L, R, R_max):
            left_idx = bisect.bisect_left(wa_positions, L)
            right_idx = bisect.bisect_right(wa_positions, R) -1
            if left_idx > right_idx:
                return 0
            return self._query(1, 0, self.size-1, left_idx, right_idx, R_max)
        
        def _query(self, node, node_L, node_R, q_L, q_R, R_max):
            if node_R < q_L or node_L > q_R:
                return 0
            if q_L <= node_L and node_R <= q_R:
                cnt = bisect.bisect_right(self.tree[node], R_max)
                return cnt
            mid = (node_L + node_R) //2
            return self._query(2*node, node_L, mid, q_L, q_R, R_max) + self._query(2*node+1, mid+1, node_R, q_L, q_R, R_max)
    
    wa_segment_tree = WASegmentTree(wa_positions, wa_next_ac)
    
    # Process queries
    output = []
    for _ in range(Q):
        L = int(data[idx])
        R = int(data[idx+1])
        idx +=2
        
        count = ac_segment_tree.query(L, R, R)
        penalty = wa_segment_tree.query(L, R, R)
        output.append(f"{count} {penalty}")
    
    print('\n'.join(output))
    
if __name__ == '__main__':
    main()
0