結果

問題 No.2338 Range AtCoder Query
ユーザー lam6er
提出日時 2025-04-15 22:06:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,593 bytes
コンパイル時間 407 ms
コンパイル使用メモリ 81,884 KB
実行使用メモリ 263,840 KB
最終ジャッジ日時 2025-04-15 22:08:26
合計ジャッジ時間 51,827 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

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

    submissions = []
    ac_pos = defaultdict(list)
    for i in range(N):
        p = int(input[ptr])
        s = input[ptr+1]
        ptr +=2
        submissions.append((p, s))
        if s == 'AC':
            ac_pos[p].append(i+1)  # 1-based

    # Precompute next_ac for each WA submission
    next_ac = [0] * (N + 2)  # 1-based
    for i in range(1, N+1):
        p, s = submissions[i-1]
        if s == 'WA':
            lst = ac_pos.get(p, [])
            idx = bisect.bisect_right(lst, i)
            if idx < len(lst):
                next_ac[i] = lst[idx]
            else:
                next_ac[i] = float('inf')
        else:
            next_ac[i] = 0  # mark as not WA

    # Prepare data for WA submissions and their next_ac
    wa_positions = []
    wa_next_ac = []
    sum_wa = [0] * (N + 1)
    for i in range(1, N+1):
        sum_wa[i] = sum_wa[i-1] + (1 if submissions[i-1][1] == 'WA' else 0)
        if submissions[i-1][1] == 'WA':
            wa_positions.append(i)
            wa_next_ac.append(next_ac[i])

    # Segment Tree for wa_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):
                self.tree[self.size + i] = [data[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, x):
            res = 0
            l += self.size
            r += self.size
            while l < r:
                if l % 2 == 1:
                    res += bisect.bisect_right(self.tree[l], x)
                    l += 1
                if r % 2 == 1:
                    r -= 1
                    res += bisect.bisect_right(self.tree[r], x)
                l >>= 1
                r >>= 1
            return res

    st = SegmentTree(wa_next_ac) if wa_next_ac else None

    # Process queries for correct count using BIT
    queries = []
    for q in range(Q):
        L = int(input[ptr])
        R = int(input[ptr+1])
        ptr +=2
        queries.append((L, R, q))

    # Sort queries by R
    queries_sorted = sorted(queries, key=lambda x: x[1])

    # Prepare AC events sorted by position
    ac_events = []
    for i in range(1, N+1):
        p, s = submissions[i-1]
        if s == 'AC':
            ac_events.append((i, p))

    # 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 = [0]*(M+2)
    res_correct = [0]*Q

    event_ptr = 0
    for L, R, q_idx in queries_sorted:
        while event_ptr < len(ac_events) and ac_events[event_ptr][0] <= R:
            pos, p = ac_events[event_ptr]
            if last_occurrence[p] < pos:
                if last_occurrence[p] > 0:
                    bit.add(last_occurrence[p], -1)
                bit.add(pos, 1)
                last_occurrence[p] = pos
            event_ptr +=1
        # Query number of elements >= L
        total = bit.query(R)
        exclude = bit.query(L-1)
        res_correct[q_idx] = total - exclude

    # Process each query to compute penalty
    res_penalty = [0]*Q
    for L, R, q_idx in queries:
        # Find WA submissions in [L, R]
        if not wa_positions:
            penalty = 0
        else:
            left = bisect.bisect_left(wa_positions, L)
            right_idx = bisect.bisect_right(wa_positions, R)
            if left >= right_idx:
                penalty = 0
            else:
                penalty = st.query(left, right_idx, R)
        res_penalty[q_idx] = penalty

    # Reorder the results and output
    output = ['']*Q
    for i in range(Q):
        L, R, q_idx = queries[i]
        correct = res_correct[q_idx]
        penalty = res_penalty[q_idx]
        output[q_idx] = f"{correct} {penalty}"
    
    print('\n'.join(output))

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