結果

問題 No.1998 Manhattan Restaurant
ユーザー lam6er
提出日時 2025-04-16 00:05:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,833 bytes
コンパイル時間 428 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 209,108 KB
最終ジャッジ日時 2025-04-16 00:07:32
合計ジャッジ時間 5,899 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 WA * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    houses = []
    index = 1
    for _ in range(N):
        X = int(data[index])
        Y = int(data[index + 1])
        index += 2
        u = X + Y
        v = X - Y
        houses.append((u, v))
    
    low = 0
    high = 2 * 10**18
    answer = high
    
    while low <= high:
        mid = (low + high) // 2
        
        # Check single point coverage
        max_u_low = -float('inf')
        min_u_high = float('inf')
        max_v_low = -float('inf')
        min_v_high = float('inf')
        for u, v in houses:
            u_low = u - mid
            u_high = u + mid
            v_low = v - mid
            v_high = v + mid
            if u_low > max_u_low:
                max_u_low = u_low
            if u_high < min_u_high:
                min_u_high = u_high
            if v_low > max_v_low:
                max_v_low = v_low
            if v_high < min_v_high:
                min_v_high = v_high
        
        if max_u_low <= min_u_high and max_v_low <= min_v_high:
            answer = mid
            high = mid - 1
            continue
        
        # Prepare house info for the current mid
        house_info = []
        for u, v in houses:
            u_low = u - mid
            u_high = u + mid
            v_low = v - mid
            v_high = v + mid
            house_info.append((u_low, u_high, v_low, v_high))
        
        feasible = False
        # Check four possible sorted orders
        for sorted_list in [
            sorted(house_info, key=lambda x: x[0]),  # u_low
            sorted(house_info, key=lambda x: x[1]),  # u_high
            sorted(house_info, key=lambda x: x[2]),  # v_low
            sorted(house_info, key=lambda x: x[3])   # v_high
        ]:
            n = len(sorted_list)
            # Compute prefix arrays
            prefix_max_u_low = [-float('inf')] * (n + 1)
            prefix_min_u_high = [float('inf')] * (n + 1)
            prefix_max_v_low = [-float('inf')] * (n + 1)
            prefix_min_v_high = [float('inf')] * (n + 1)
            for i in range(1, n + 1):
                prefix_max_u_low[i] = max(prefix_max_u_low[i-1], sorted_list[i-1][0])
                prefix_min_u_high[i] = min(prefix_min_u_high[i-1], sorted_list[i-1][1])
                prefix_max_v_low[i] = max(prefix_max_v_low[i-1], sorted_list[i-1][2])
                prefix_min_v_high[i] = min(prefix_min_v_high[i-1], sorted_list[i-1][3])
            
            # Compute suffix arrays
            suffix_max_u_low = [-float('inf')] * (n + 1)
            suffix_min_u_high = [float('inf')] * (n + 1)
            suffix_max_v_low = [-float('inf')] * (n + 1)
            suffix_min_v_high = [float('inf')] * (n + 1)
            for i in range(n-1, -1, -1):
                suffix_max_u_low[i] = max(suffix_max_u_low[i+1], sorted_list[i][0])
                suffix_min_u_high[i] = min(suffix_min_u_high[i+1], sorted_list[i][1])
                suffix_max_v_low[i] = max(suffix_max_v_low[i+1], sorted_list[i][2])
                suffix_min_v_high[i] = min(suffix_min_v_high[i+1], sorted_list[i][3])
            
            # Check all possible splits
            for k in range(1, n):
                s1_ok = (prefix_max_u_low[k] <= prefix_min_u_high[k]) and (prefix_max_v_low[k] <= prefix_min_v_high[k])
                s2_ok = (suffix_max_u_low[k] <= suffix_min_u_high[k]) and (suffix_max_v_low[k] <= suffix_min_v_high[k])
                if s1_ok and s2_ok:
                    feasible = True
                    break
            if feasible:
                break
        
        if feasible:
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    
    print(answer)

if __name__ == '__main__':
    main()
0