結果
問題 |
No.2338 Range AtCoder Query
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:47:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,345 bytes |
コンパイル時間 | 240 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 80,432 KB |
最終ジャッジ日時 | 2025-06-12 18:48:02 |
合計ジャッジ時間 | 11,459 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 5 WA * 5 TLE * 1 -- * 23 |
ソースコード
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()