結果
問題 |
No.1074 増殖
|
ユーザー |
![]() |
提出日時 | 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()