結果
| 問題 |
No.449 ゆきこーだーの雨と雪 (4)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:20:25 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,615 bytes |
| コンパイル時間 | 526 ms |
| コンパイル使用メモリ | 82,744 KB |
| 実行使用メモリ | 225,336 KB |
| 最終ジャッジ日時 | 2025-05-14 13:21:57 |
| 合計ジャッジ時間 | 15,696 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 8 WA * 35 |
ソースコード
import sys
# Fenwick Tree (Binary Indexed Tree) Implementation
# Uses 1-based indexing internally. Tree stores values for indices 1 through size.
class FenwickTree:
"""
A Fenwick Tree (Binary Indexed Tree) supporting point updates and prefix sum queries.
It uses 1-based indexing internally for array access, but methods accept standard indices.
"""
def __init__(self, size):
"""
Initializes a Fenwick Tree supporting indices up to `size`.
The internal tree array will have size `size + 1`.
"""
# The internal array size needs to be size + 1 to handle index `size`.
self.tree = [0] * (size + 1)
def update(self, k, delta):
"""
Adds `delta` to the value at index `k`.
Assumes `k` is 1-based index.
"""
# Ensure k is within the valid range [1, size]
if k <= 0:
# Index must be positive for 1-based indexing.
# Depending on context, might raise error or silently ignore.
# Let's ignore for robustness against potential edge cases like time 0.
return
_size = len(self.tree)
while k < _size:
self.tree[k] += delta
# Move to the next index that k contributes to
k += k & (-k)
def query(self, k):
"""
Computes the prefix sum up to index `k` (sum of values for indices 1, 2, ..., k).
Assumes `k` is 1-based index.
"""
# If k is 0 or less, the prefix sum is 0.
if k <= 0:
return 0
# Ensure k does not exceed the maximum index supported by the tree structure.
_size = len(self.tree)
# Clamp k to the maximum valid index if it's too large.
k = min(k, _size - 1)
s = 0
while k > 0:
s += self.tree[k]
# Move to the index responsible for the next lower range
k -= k & (-k)
return s
def solve():
"""
Main function to solve the problem. Reads input, processes events, and prints output.
"""
N = int(sys.stdin.readline())
L_str = sys.stdin.readline().split()
L = [int(x) for x in L_str]
T = int(sys.stdin.readline())
# Map problem characters ('A', 'B', ...) to their levels (scores)
problem_levels = {}
for i in range(N):
problem_char = chr(ord('A') + i)
problem_levels[problem_char] = L[i]
# Calculate the maximum possible score a participant can achieve.
# This is the sum of all problem levels.
max_score_actual = sum(L)
# Dictionary to store the state of each participant.
# Key: participant name (str)
# Value: dictionary {'score': int, 'time': int, 'solved': set}
# 'score' is the total score.
# 'time' is the timestamp of the last submission that increased the score.
# 'solved' is a set of problem characters solved by the participant.
participants = {}
# Fenwick tree to store counts of participants for each score value.
# It supports scores from 0 up to max_score_actual.
# We use 1-based indexing for the Fenwick tree: score `s` corresponds to index `s + 1`.
# The size needed is max_score_actual + 1 to support the index for the maximum score.
score_count_tree = FenwickTree(max_score_actual + 1)
# A list where each element is a Fenwick tree.
# score_time_trees[s] is a Fenwick tree managing submission times for participants currently having score `s`.
# This list is indexed directly by score `s` (from 0 to max_score_actual).
# Each time-based Fenwick tree supports times from 1 up to T. The size needed is T.
score_time_trees = [FenwickTree(T) for _ in range(max_score_actual + 1)]
results = [] # List to store the ranks calculated for query ('?') operations.
# Process events chronologically from time 1 to T.
for current_time in range(1, T + 1):
line = sys.stdin.readline().split()
name = line[0]
action = line[1] # Either a problem character ('A', 'B', ...) or '?'
if action == '?':
# This is a query for the rank of participant 'name'.
# The problem constraints guarantee that 'name' must exist in 'participants'
# because a query is only made if the participant has made at least one submission before.
my_state = participants[name]
my_score = my_state['score']
my_time = my_state['time']
# Calculate the rank based on score and time:
# Rank = 1 + (number of participants strictly better than 'name')
# A participant 'other' is strictly better if:
# other_score > my_score
# OR (other_score == my_score AND other_time < my_time)
# Count participants with score > my_score:
# This is (Total number of participants tracked) - (Number of participants with score <= my_score)
# Total participants tracked = score_count_tree.query(max_score_actual + 1)
# Participants with score <= my_score = score_count_tree.query(my_score + 1) (using 1-based index for score)
count_better_score = score_count_tree.query(max_score_actual + 1) - score_count_tree.query(my_score + 1)
# Count participants with score == my_score and time < my_time:
# Query the Fenwick tree specific to 'my_score' (score_time_trees[my_score]).
# We need the sum of counts for times from 1 up to 'my_time - 1'.
count_same_score_better_time = score_time_trees[my_score].query(my_time - 1)
# The rank is 1 plus the total count of better participants.
rank = count_better_score + count_same_score_better_time + 1
results.append(str(rank))
else:
# This is a submission event for problem 'action' by participant 'name'.
problem_char = action
# Retrieve the level (score) for the submitted problem.
# Based on constraints, problem_char will be a valid problem ID.
problem_level = problem_levels[problem_char]
is_state_updated = False # Flag to check if this submission changes the participant's state
if name in participants:
# Participant already exists in the system.
current_state = participants[name]
# Check if this problem has already been solved by this participant.
# The problem constraints state that duplicate submissions (Name, P) don't occur.
# However, this check is robust.
if problem_char not in current_state['solved']:
# This is a new problem solved by this participant. Update their state.
is_state_updated = True
# Store the old state before update, needed for Fenwick Tree adjustments.
old_score = current_state['score']
old_time = current_state['time']
# Calculate the new state after solving this problem.
new_score = old_score + problem_level
new_time = current_time # The time of this event is the new last update time.
# Update the participant's record in the dictionary.
current_state['solved'].add(problem_char)
current_state['score'] = new_score
current_state['time'] = new_time
# Update Fenwick Trees to reflect the state change:
# 1. Remove the contribution of the old state.
score_count_tree.update(old_score + 1, -1) # Decrement count for old score (1-based index)
score_time_trees[old_score].update(old_time, -1) # Remove old time from the tree for old score
# 2. Add the contribution of the new state.
score_count_tree.update(new_score + 1, 1) # Increment count for new score (1-based index)
score_time_trees[new_score].update(new_time, 1) # Add new time to the tree for new score
else:
# This is the first submission for this participant 'name'.
is_state_updated = True
# Calculate the initial state after this first submission.
new_score = problem_level
new_time = current_time
# Add the new participant's record to the dictionary.
participants[name] = {'score': new_score, 'time': new_time, 'solved': {problem_char}}
# Update Fenwick Trees to add the new participant's state:
# Increment count for the new score (1-based index)
score_count_tree.update(new_score + 1, 1)
# Add the submission time to the time tree for the new score
score_time_trees[new_score].update(new_time, 1)
# If is_state_updated is False, it means the participant submitted a problem they had already solved.
# In this scenario, their score and last submission time do not change, and no updates to Fenwick trees are needed.
# After processing all T events, print the collected results for all queries.
# Each result should be on a new line.
print("\n".join(results))
# Execute the main function to run the solution.
solve()