結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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()
0