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()