結果
問題 |
No.2338 Range AtCoder Query
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:37:19 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,199 bytes |
コンパイル時間 | 236 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 77,236 KB |
最終ジャッジ日時 | 2025-03-20 20:38:12 |
合計ジャッジ時間 | 9,829 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 TLE * 1 -- * 23 |
ソースコード
import bisect def main(): import sys input = sys.stdin.read data = input().split() ptr = 0 N = int(data[ptr]); ptr +=1 M = int(data[ptr]); ptr +=1 Q = int(data[ptr]); ptr +=1 submissions = [] sorted_acs = [] problem_submissions = [[] for _ in range(M+1)] # 1-based indexing prefix_wa = [[] for _ in range(M+1)] ac_indices = [[] for _ in range(M+1)] for idx in range(N): p = int(data[ptr]); ptr +=1 s = data[ptr]; ptr +=1 submissions.append( (p, s) ) problem_submissions[p].append(idx) if s == 'AC': sorted_acs.append(idx) ac_indices[p].append(idx) sorted_acs.sort() # Precompute prefix_wa for each problem for p in range(1, M+1): subs = problem_submissions[p] prefix = [0] cnt = 0 for i in subs: if submissions[i][1] == 'WA': cnt += 1 prefix.append(cnt) prefix_wa[p] = prefix # Process each query output = [] for _ in range(Q): L = int(data[ptr]); ptr +=1 R = int(data[ptr]); ptr +=1 # Convert to 0-based L0 = L -1 R0 = R -1 left = bisect.bisect_left(sorted_acs, L0) right_idx = bisect.bisect_right(sorted_acs, R0) acs_in_query = sorted_acs[left:right_idx] processed = set() count = 0 penalty = 0 for s in acs_in_query: p = submissions[s][0] if p not in processed: processed.add(p) subs_p = problem_submissions[p] # Find submissions >= L0 and < s left_sub = bisect.bisect_left(subs_p, L0) # Find first submission >= s is the position where s is found right_sub = bisect.bisect_left(subs_p, s) # Number of WA in [left_sub, right_sub) wa = prefix_wa[p][right_sub] - prefix_wa[p][left_sub] penalty += wa count += 1 output.append(f"{count} {penalty}") print('\n'.join(output)) if __name__ == "__main__": main()