結果
| 問題 |
No.2338 Range AtCoder Query
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-15 21:59:33 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,910 bytes |
| コンパイル時間 | 291 ms |
| コンパイル使用メモリ | 82,152 KB |
| 実行使用メモリ | 79,656 KB |
| 最終ジャッジ日時 | 2025-04-15 22:00:46 |
| 合計ジャッジ時間 | 8,795 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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()