結果
| 問題 |
No.2338 Range AtCoder Query
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:09:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,888 bytes |
| コンパイル時間 | 190 ms |
| コンパイル使用メモリ | 82,180 KB |
| 実行使用メモリ | 457,168 KB |
| 最終ジャッジ日時 | 2025-05-14 13:11:27 |
| 合計ジャッジ時間 | 46,783 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 6 WA * 28 |
ソースコード
import sys
# Set higher recursion depth if needed, although BIT operations are iterative.
# sys.setrecursionlimit(200010)
def solve():
# Use fast I/O
input = sys.stdin.readline
N, M, Q = map(int, input().split())
submissions = []
for i in range(N):
line = input().split()
# Store problem ID, result string, and 0-based index 'k'
submissions.append({'p': int(line[0]), 's': line[1], 'k': i})
queries = []
for i in range(Q):
l, r = map(int, input().split())
# Store query range [L, R] (1-based) and original query ID
queries.append({'L': l, 'R': r, 'id': i})
# --- Precomputation ---
# Group submission indices by problem ID
problem_submissions = {} # p_id -> list of 0-based indices k
for i in range(N):
p = submissions[i]['p']
if p not in problem_submissions:
problem_submissions[p] = []
problem_submissions[p].append(i)
# Stores pairs (k', k_nextAC) for penalty calculation using 1-based indices
wa_points = []
# Stores events for accepted count calculation using 1-based indices
ac_events = []
# Stores the 1-based index of the last AC submission encountered for each problem ID
last_ac_idx = {}
# Iterate through problems to find necessary relationships for events/points generation
problem_ids = list(problem_submissions.keys()) # Get keys once for efficiency
for p in problem_ids:
indices = problem_submissions[p] # List of 0-based indices k for problem p
# Precompute the index of the next AC submission for each submission related to problem p
next_ac_for_k = {} # Maps 0-based index k -> 1-based index of the next AC for problem p
last_ac_k_1based_in_pass = -1 # Track the 1-based index of the last AC found in reverse pass
# Iterate backwards through submissions for problem p to find the next AC efficiently
for i in range(len(indices) - 1, -1, -1):
k = indices[i] # Current submission's 0-based index
if submissions[k]['s'] == 'AC':
# Update the last seen AC index (1-based)
last_ac_k_1based_in_pass = k + 1
# If an AC has been seen, store it as the 'next AC' for index k
if last_ac_k_1based_in_pass != -1:
# The found AC index must be strictly after the current index k
if last_ac_k_1based_in_pass > k + 1:
next_ac_for_k[k] = last_ac_k_1based_in_pass
# Iterate forwards through submissions for problem p to generate WA points and AC events
for i in range(len(indices)):
k = indices[i] # Current submission's 0-based index
k_1based = k + 1 # Current submission's 1-based index
if submissions[k]['s'] == 'WA':
# If this WA submission has a corresponding next AC
if k in next_ac_for_k:
k_nextAC_1based = next_ac_for_k[k]
# Add a point (k', k_nextAC) for penalty calculation
# x=k_1based (WA index), y=k_nextAC_1based (Next AC index)
wa_points.append({'x': k_1based, 'y': k_nextAC_1based})
elif submissions[k]['s'] == 'AC':
k_curr_ac_1based = k_1based # Current AC's 1-based index
# Fetch the 1-based index of the previous AC for this problem, default 0 if none
k_prev_ac_1based = last_ac_idx.get(p, 0)
# Create events for accepted count calculation based on the interval of L values
# where this AC is the first one.
# Add event: effect starts at L = k_prev_ac + 1
# Sub event: effect ends at L = k_curr_ac + 1
ac_events.append({'type': 'add', 'x': k_prev_ac_1based + 1, 'k': k_curr_ac_1based})
ac_events.append({'type': 'sub', 'x': k_curr_ac_1based + 1, 'k': k_curr_ac_1based})
# Update the last seen AC index for problem p
last_ac_idx[p] = k_curr_ac_1based
# --- Fenwick Tree (Binary Indexed Tree - BIT) Class ---
class FenwickTree:
def __init__(self, size):
# Initialize BIT with zeros, size+1 for 1-based indexing
self.tree = [0] * (size + 1)
self.size = size
def add(self, i, delta):
# Add delta to index i. Indices must be within [1, size]
if not (1 <= i <= self.size):
return # Ignore updates outside valid range
# Standard BIT update: move to parent indices
while i <= self.size:
self.tree[i] += delta
i += i & (-i) # Move to next index that covers i
def query_prefix(self, i):
# Query sum of values in range [1, i]
# Clamp index i to valid range [0, size]
if i > self.size: i = self.size
if i < 0: return 0
s = 0
# Standard BIT query: move to parent indices covering prefix ending at i
while i > 0:
s += self.tree[i]
i -= i & (-i) # Move to index covering prefix before i's range
return s
def query(self, l, r):
# Query sum of values in range [l, r]
if r < l: return 0
# Compute using prefix sums: sum(1..r) - sum(1..l-1)
return self.query_prefix(r) - self.query_prefix(l - 1)
# Array to store final results for each query (Accepted Count, Penalty)
results = [(0, 0)] * Q
# --- Calculate Penalties using Sweep Line on R ---
# Sort queries by their right endpoint R
queries_sorted_R = sorted(queries, key=lambda q: q['R'])
# Sort WA points by their y coordinate (k_nextAC)
wa_points.sort(key=lambda p: p['y'])
bit_pen = FenwickTree(N) # BIT to track active WA contributions based on x coordinate (k')
pt_idx = 0 # Pointer for wa_points array
# Sweep line moves across R from 1 to N
for q in queries_sorted_R:
R = q['R'] # Current sweep line position
# Add contributions from WA points whose next AC index (y coordinate) is <= R
while pt_idx < len(wa_points) and wa_points[pt_idx]['y'] <= R:
# Add +1 at index x (WA position k') in the BIT
bit_pen.add(wa_points[pt_idx]['x'], 1)
pt_idx += 1
# Query penalty for the current query (L, R)
# We need count of points (x, y) such that L <= x and y <= R.
# BIT state reflects points with y <= R. Query sums counts for x >= L.
current_penalty = bit_pen.query(q['L'], N) # Sum counts for x in range [L, N]
# Store the calculated penalty in the results array using original query ID
results[q['id']] = (results[q['id']][0], current_penalty)
# --- Calculate Accepted Counts using Sweep Line on L ---
# Sort queries by their left endpoint L
queries_sorted_L = sorted(queries, key=lambda q: q['L'])
# Sort AC events by their x coordinate (effective L value)
ac_events.sort(key=lambda e: e['x'])
bit_acc = FenwickTree(N) # BIT to track active AC contributions based on k coordinate
event_idx = 0 # Pointer for ac_events array
# Sweep line moves across L from 1 to N
for q in queries_sorted_L:
L = q['L'] # Current sweep line position
# Process all AC events whose effective L coordinate (x) is <= current L
while event_idx < len(ac_events) and ac_events[event_idx]['x'] <= L:
event = ac_events[event_idx]
k = event['k'] # The index k (1-based) whose contribution is changing
# Update BIT based on event type ('add' or 'sub')
if event['type'] == 'add':
bit_acc.add(k, 1)
else: # 'sub'
bit_acc.add(k, -1)
event_idx += 1
# Query accepted count for the current query (L, R)
# We need sum of active contributions for indices k in [1, R]
# BIT state reflects contributions active for sweep line position L.
current_acc_count = bit_acc.query(1, q['R']) # Sum contributions for k in range [1, R]
# Update the results tuple with accepted count, retrieving the already computed penalty
pen = results[q['id']][1] # Fetch penalty computed in the previous phase
results[q['id']] = (current_acc_count, pen)
# --- Output results ---
# Prepare output lines efficiently
output_lines = [f"{results[i][0]} {results[i][1]}" for i in range(Q)]
# Print all lines at once joined by newline
print('\n'.join(output_lines))
solve()