結果
問題 |
No.2338 Range AtCoder Query
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:08:54 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,557 bytes |
コンパイル時間 | 402 ms |
コンパイル使用メモリ | 81,840 KB |
実行使用メモリ | 229,360 KB |
最終ジャッジ日時 | 2025-04-15 22:10:29 |
合計ジャッジ時間 | 48,109 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 2 WA * 32 |
ソースコード
import sys import bisect from collections import defaultdict def main(): sys.setrecursionlimit(1 << 25) input = sys.stdin.read().split() ptr = 0 N, M, Q = map(int, input[ptr:ptr+3]) ptr +=3 P = [] S = [] for _ in range(N): p = int(input[ptr]) s = input[ptr+1] ptr +=2 P.append(p) S.append(s) # Preprocess next_ac for WA submissions problem_ac = defaultdict(list) for i in range(N): if S[i] == 'AC': problem_ac[P[i]].append(i+1) # 1-based next_ac = [0]*(N+2) # 1-based for i in range(1, N+1): if S[i-1] == 'WA': p = P[i-1] ac_list = problem_ac.get(p, []) idx = bisect.bisect_right(ac_list, i) if idx < len(ac_list): next_ac[i] = ac_list[idx] else: next_ac[i] = float('inf') else: next_ac[i] = float('inf') # Build segment tree for WA submissions' 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): if S[i] == 'WA': self.tree[self.size + i] = [next_ac[i+1]] # data is 0-based, next_ac is 1-based else: self.tree[self.size + 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, R): res = 0 l += self.size -1 # convert to 1-based in the tree r += self.size while l < r: if l %2 ==1: res += bisect.bisect_right(self.tree[l], R) l +=1 if r %2 ==1: r -=1 res += bisect.bisect_right(self.tree[r], R) l >>=1 r >>=1 return res # Prepare data for segment tree (WA submissions) data = [i+1 for i in range(N) if S[i] == 'WA'] st = SegmentTree([(i+1) for i in range(N)]) # Process AC submissions for correct count using BIT ac_indices = [] for i in range(N): if S[i] == 'AC': ac_indices.append(i+1) # 1-based # Build 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 = {} for j in ac_indices: p = P[j-1] if p in last_occurrence: prev_j = last_occurrence[p] bit.add(prev_j, -1) bit.add(j, 1) last_occurrence[p] = j # Process queries output = [] for _ in range(Q): L = int(input[ptr]) R = int(input[ptr+1]) ptr +=2 # Correct count correct = bit.query(R) - bit.query(L-1) # Penalty count penalty = st.query(L, R, R) output.append(f"{correct} {penalty}") print('\n'.join(output)) if __name__ == '__main__': main()