結果
| 問題 |
No.1074 増殖
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:20:17 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,679 bytes |
| コンパイル時間 | 202 ms |
| コンパイル使用メモリ | 82,692 KB |
| 実行使用メモリ | 135,260 KB |
| 最終ジャッジ日時 | 2025-05-14 13:21:05 |
| 合計ジャッジ時間 | 5,457 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 4 TLE * 1 -- * 7 |
ソースコード
import sys
sys.setrecursionlimit(2 * 10**5) # Increased recursion limit
def solve():
N = int(sys.stdin.readline())
rects_input = []
if N == 0:
return
for _ in range(N):
rects_input.append(list(map(int, sys.stdin.readline().split())))
all_x_coords = set()
all_y_coords = set()
for r_idx, r in enumerate(rects_input):
xa, ya, xb, yb = r
all_x_coords.add(xa)
all_x_coords.add(xb)
all_y_coords.add(ya)
all_y_coords.add(yb)
sorted_x = sorted(list(all_x_coords))
sorted_y = sorted(list(all_y_coords))
map_x_to_idx = {val: i for i, val in enumerate(sorted_x)}
map_y_to_idx = {val: i for i, val in enumerate(sorted_y)}
y_tree_node_store = {}
x_tree_node_store = {}
next_y_tree_id_counter = 0
def get_y_node_obj(tree_id, node_idx):
key = (tree_id, node_idx)
if key not in y_tree_node_store:
y_tree_node_store[key] = {'val': 0, 'tag': False, 'total_len': 0}
return y_tree_node_store[key]
def update_y_seg_tree_recursive(tree_id, y_node_idx,
node_y_start_idx, node_y_end_idx,
target_y_start_idx, target_y_end_idx):
node_obj = get_y_node_obj(tree_id, y_node_idx)
if node_obj['total_len'] == 0:
node_obj['total_len'] = sorted_y[node_y_end_idx] - sorted_y[node_y_start_idx]
if node_obj['tag'] or node_obj['total_len'] == 0: # Already fully covered or zero-length interval
return 0
if node_y_end_idx <= target_y_start_idx or \
node_y_start_idx >= target_y_end_idx: # Disjoint
return 0
if target_y_start_idx <= node_y_start_idx and \
node_y_end_idx <= target_y_end_idx: # Current node's interval is fully within target
increase_in_len = node_obj['total_len'] - node_obj['val']
node_obj['val'] = node_obj['total_len']
node_obj['tag'] = True
return increase_in_len
if node_y_start_idx + 1 == node_y_end_idx: # Leaf of y-tree
# This path for a leaf that is not fully contained by target and not disjoint should not be hit.
return 0
mid_y_idx = (node_y_start_idx + node_y_end_idx) // 2
left_child_idx = 2 * y_node_idx
right_child_idx = 2 * y_node_idx + 1
# Ensure children total_len are initialized before recursive calls affect their 'val'
# This is important because parent 'val' depends on children 'val'
get_y_node_obj(tree_id, left_child_idx)['total_len'] = sorted_y[mid_y_idx] - sorted_y[node_y_start_idx]
get_y_node_obj(tree_id, right_child_idx)['total_len'] = sorted_y[node_y_end_idx] - sorted_y[mid_y_idx]
inc_L = update_y_seg_tree_recursive(tree_id, left_child_idx,
node_y_start_idx, mid_y_idx,
target_y_start_idx, target_y_end_idx)
inc_R = update_y_seg_tree_recursive(tree_id, right_child_idx,
mid_y_idx, node_y_end_idx,
target_y_start_idx, target_y_end_idx)
old_val = node_obj['val']
node_obj['val'] = get_y_node_obj(tree_id, left_child_idx)['val'] + \
get_y_node_obj(tree_id, right_child_idx)['val']
if node_obj['val'] == node_obj['total_len']: # Use exact comparison for integers
node_obj['tag'] = True
return node_obj['val'] - old_val
def get_x_node_obj(node_idx):
if node_idx not in x_tree_node_store:
x_tree_node_store[node_idx] = {'area_val': 0} # area_val is sum of children's area_val or strip_area for leaf
return x_tree_node_store[node_idx]
def update_x_seg_tree_recursive(x_node_idx,
node_x_start_idx, node_x_end_idx,
target_x_start_idx, target_x_end_idx,
target_y_start_idx, target_y_end_idx):
nonlocal next_y_tree_id_counter
node_obj = get_x_node_obj(x_node_idx)
current_strip_total_width = sorted_x[node_x_end_idx] - sorted_x[node_x_start_idx]
if node_x_end_idx <= target_x_start_idx or \
node_x_start_idx >= target_x_end_idx or \
current_strip_total_width == 0:
return 0
if node_x_start_idx + 1 == node_x_end_idx: # Leaf of X-tree (elementary x-strip)
actual_strip_width = current_strip_total_width
if 'y_tree_id' not in node_obj:
node_obj['y_tree_id'] = next_y_tree_id_counter
y_root_node_obj = get_y_node_obj(next_y_tree_id_counter, 1)
y_root_node_obj['total_len'] = sorted_y[len(sorted_y)-1] - sorted_y[0]
next_y_tree_id_counter += 1
y_tree_id = node_obj['y_tree_id']
num_distinct_y_coords = len(sorted_y)
if num_distinct_y_coords <= 1: return 0
increase_in_y_len = update_y_seg_tree_recursive(y_tree_id, 1,
0, num_distinct_y_coords - 1,
target_y_start_idx, target_y_end_idx)
increase_in_area_for_strip = actual_strip_width * increase_in_y_len
node_obj['area_val'] += increase_in_area_for_strip # area_val of x-leaf is total covered area IN THIS STRIP
return increase_in_area_for_strip
# Internal X-node
mid_x_idx = (node_x_start_idx + node_x_end_idx) // 2
inc_L = update_x_seg_tree_recursive(2 * x_node_idx,
node_x_start_idx, mid_x_idx,
target_x_start_idx, target_x_end_idx,
target_y_start_idx, target_y_end_idx)
inc_R = update_x_seg_tree_recursive(2 * x_node_idx + 1,
mid_x_idx, node_x_end_idx,
target_x_start_idx, target_x_end_idx,
target_y_start_idx, target_y_end_idx)
node_obj['area_val'] = get_x_node_obj(2*x_node_idx)['area_val'] + \
get_x_node_obj(2*x_node_idx+1)['area_val']
return inc_L + inc_R
results_output = []
num_distinct_x_coords = len(sorted_x)
num_distinct_y_coords = len(sorted_y)
if num_distinct_x_coords <= 1 or num_distinct_y_coords <= 1:
for _ in range(N):
results_output.append(0)
else:
for r_coords in rects_input:
Xa, Ya, Xb, Yb = r_coords
xa_idx = map_x_to_idx[Xa]
xb_idx = map_x_to_idx[Xb]
ya_idx = map_y_to_idx[Ya]
yb_idx = map_y_to_idx[Yb]
if xa_idx == xb_idx or ya_idx == yb_idx:
results_output.append(0)
continue
increase = update_x_seg_tree_recursive(1,
0, num_distinct_x_coords - 1, # X-tree root covers all x_coord_indices intervals
xa_idx, xb_idx, # Target x-coord_indices intervals
ya_idx, yb_idx) # Target y-coord_indices intervals
results_output.append(increase)
for res in results_output:
print(res)
solve()