結果
問題 |
No.2338 Range AtCoder Query
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()