#1189821 (PyPy3) No.2436 Min Diff Distance

• 問題: No.2436 Min Diff Distance
• ユーザー: LyricalMaestro
• 提出日時: 2026-09-20 18:16:07
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 1,472 ms / 2,000 ms
• コード長: 4,085 bytes
• コンパイル時間: 81 ms
• コンパイル使用メモリ: 83,672 KB
• 実行使用メモリ: 159,888 KB
• 最終ジャッジ日時: 2026-09-20 18:16:30
• 合計ジャッジ時間: 22,933 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
other	AC * 23

ソースコード

## https://yukicoder.me/problems/no/2436

MAX_INT = 10 ** 18

class SegmentTree:
    """
    非再帰版セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    """

    def __init__(self, init_array):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        self.array = [MAX_INT] * (2 * self.size)
        for i, a in enumerate(init_array):
            self.array[self.size + i] = a
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                self.array[i] = min(self.array[2 * i], self.array[2 * i + 1])
            end_index = start_index
            start_index = end_index // 2

    def set(self, x, a):
        index = self.size + x
        self.array[index] = a
        while index > 1:
            index //= 2
            self.array[index] = min(self.array[2 * index], self.array[2 * index + 1])

    def get_min(self, l, r):
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        s = MAX_INT
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.array[R])
            if L & 1:
                s = min(s, self.array[L])
                L += 1
            L >>= 1; R >>= 1
        return s


def calc_max(N, xy):
    u_list = []
    v_list = []
    for i in range(N):
        x, y = xy[i]
        u = x + y
        v = x - y
        u_list.append((u, i))
        v_list.append((v, i))

    u_list.sort(key=lambda x :x[0])
    v_list.sort(key=lambda x :x[0])

    min_answer = [-MAX_INT] * N
    for i in range(N):
        u, index = u_list[i]
        min_answer[index] = max(u_list[-1][0] - u, u - u_list[0][0], min_answer[index])
    for i in range(N):
        v, index = v_list[i]
        min_answer[index] = max(v_list[-1][0] - v, v - v_list[0][0], min_answer[index])

    return min_answer

def calc_min(N, xy):
    xy_array = [(i, xy[i][0], xy[i][1]) for i in range(N)]

    xy_array.sort(key=lambda x :x[1])

    answers = [MAX_INT] * N
    # Xi >= Xi0 について Yi >= Yi0のケース YiをキーにしたXi + Yiの最小値()
    #                   Yi < Yi0のケース Yiをキーにした　Xi - Yi の最小値
    positive_seg_tree = SegmentTree([MAX_INT] * (N + 1))
    negative_seg_tree = SegmentTree([MAX_INT] * (N + 1))
    for index, x0, y0 in reversed(xy_array):
        ans_p = positive_seg_tree.get_min(y0, N + 1)
        ans_n = negative_seg_tree.get_min(0, y0)

        ans = MAX_INT
        if ans_p < MAX_INT:
            ans = min(ans, ans_p - (x0 + y0))
        if ans_n < MAX_INT: 
            ans = min(ans, ans_n - (x0 - y0))
        answers[index]  =min(answers[index], ans)

        positive_seg_tree.set(y0, x0 + y0)
        negative_seg_tree.set(y0, x0 - y0)
            

    # Xi <= Xi0 について Yi >= Yi0のケース Yiをキーにした - Xi + Yiの最小値()
    #                   Yi < Yi0のケース Yiをキーにした　-Xi - Yi の最小値
    positive_seg_tree = SegmentTree([MAX_INT] * (N + 1))
    negative_seg_tree = SegmentTree([MAX_INT] * (N + 1))
    for index, x0, y0 in xy_array:
        ans_p = positive_seg_tree.get_min(y0, N + 1)
        ans_n = negative_seg_tree.get_min(0, y0)

        ans = MAX_INT
        if ans_p < MAX_INT:
            ans = min(ans, ans_p - (-x0 + y0))
        if ans_n < MAX_INT: 
            ans = min(ans, ans_n - (-x0 - y0))
        answers[index] = min(answers[index], ans)

        positive_seg_tree.set(y0, -x0 + y0)
        negative_seg_tree.set(y0, -x0 - y0)

    return answers


def main():
    N = int(input())
    xy = []
    for _ in range(N):
        x, y = map(int, input().split())
        xy.append((x, y))

    # 最大値を求める
    max_answer = calc_max(N, xy)
    min_answer = calc_min(N, xy)

    answer = MAX_INT
    for i in range(N):
        answer = min(answer, max_answer[i] - min_answer[i])
    print(answer)





if __name__ == "__main__":
    main()