提出 #25488092

---

ソースコード 拡げる

from heapq import heappop,heappush
from collections import defaultdict
class QuasiMultiset:

    def __init__(self,deleteFlag=True):
        '''
        deleteFlag: 要素数が0となったkeyを辞書から削除するか
        '''
        self.len = 0
        self.f = defaultdict(int)
        self.pos = []
        self.neg = []
        self.deleteFlag = deleteFlag

    def _delete(self,key):
        '''
        要素数が0となったkeyを辞書から削除
        内部呼び出し用
        '''
        if self.deleteFlag and self.f[key] == 0:
            del self.f[key]

    def add(self,x,key=None):
        '''
        x:追加する要素の値
        key:キー
        '''
        if key is None:
            key = x
        self.len += 1
        heappush(self.pos,(x,key))
        heappush(self.neg,(-x,key))
        self.f[key] += 1

    def popMax(self,returnKey=False):
        '''
        最大値とそのkey(optional)をpopする
        '''
        while True:
            x,key = heappop(self.neg)
            if self.f[key]:
                self.f[key] -= 1
                self.len -= 1
                self._delete(key)
                if returnKey:
                    return -x,key
                else:
                    return x

    def popMin(self,returnKey=False):
        '''
        最小値とそのkey(optional)をpopする
        '''
        while True:
            x,key = heappop(self.pos)
            if self.f[key]:
                self.f[key] -= 1
                self.len -= 1
                self._delete(key)
                if returnKey:
                    return x,key
                else:
                    return x
            
    def seachMax(self,returnKey=False):
        '''
        最大値とそのkey(optional)をreturnする
        '''
        while True:
            x,key = self.neg[0]
            if self.f[key]:
                if returnKey:
                    return -x,key
                else:
                    return -x
            else:
                heappop(self.neg)
    
    def seachMin(self,returnKey=False):
        '''
        最小値とそのkey(optional)をreturnする
        '''
        while True:
            x,key = self.pos[0]
            if self.f[key]:
                if returnKey:
                    return x,key
                else:
                    return x
            else:
                heappop(self.pos)

    def delete(self,key):
        '''
        key:削除するkey
        '''
        self.f[key] -= 1
        self._delete(key)
        self.len -= 1

    def exist(self,key):
        t = self.f.get(key)
        if t is None:
            return False
        else:
            if self.f[t]:
                return True
            else:
                return False
N = int(input())
mins = []
maxes = []
for i in range(N):
    x,y = sorted(map(int,input().split()))
    mins.append(x)
    maxes.append(y)

def solve1():
    return (max(mins)-min(mins))*(max(maxes)-min(maxes))

def solve2():
    ms = QuasiMultiset()
    d = max(maxes)-min(mins)
    mn = [(mins[i],i) for i in range(N)]
    mn.sort()
    for i in range(N):
        ms.add(mn[i][0])
    mi = ms.seachMax()-ms.seachMin()
    for i in range(N):
        x,idx = mn[i]
        ms.delete(x)
        ms.add(maxes[idx])
        mi = min(mi,ms.seachMax()-ms.seachMin())
    return (max(maxes)-min(mins))*mi

print(min(solve1(),solve2()))

提出情報

ジャッジ結果