Problem:


Score : 700 points

Problem Statement

There are N bags, each containing two white balls. The i-th box contains two balls with integers x_i and y_i written on them, respectively.

For each of these bags, you will paint one of the balls red, and paint the other blue.

Afterwards, the 2N balls will be classified according to color.

Then, we will define the following:

R_{max}: the maximum integer written on a ball painted in red

R_{min}: the minimum integer written on a ball painted in red

B_{max}: the maximum integer written on a ball painted in blue

B_{min}: the minimum integer written on a ball painted in blue

Find the minimum possible value of (R_{max} - R_{min}) \times (B_{max} - B_{min}).

Constraints

1 ≤ N ≤ 200,000

1 ≤ x_i, y_i ≤ 10^9

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the minimum possible value.

Sample Input 1

3
1 2
3 4
5 6

Sample Output 1

15

The optimal solution is to paint the balls with x_1, x_2, y_3 red, and paint the balls with y_1, y_2, x_3 blue.

Sample Input 2

3
1010 10
1000 1
20 1020

Sample Output 2

380

Sample Input 3

2
1 1
1000000000 1000000000

Sample Output 3

999999998000000001



Sample input:
3
1 2
3 4
5 6


Sample output:
15

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = float("inf")
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import sys
    
    input=sys.stdin.readline
    
    N=int(input())
    q=[]
    init_val=[0]*N
    r=[]
    b=[]
    ball=[]
    X=0
    q_append=q.append
    for i in range(N):
        x,y=map(int,input().split())
        ball.append((x,y))
        r.append(max(x,y))
        b.append(min(x,y))
        init_val[i]=min(x,y)
        q_append((max(x,y),-1,i))
        X=max(X,min(x,y))
    
    for i in range(N):
        x,y=ball[i]
        if x>=X:
            q_append((x,i,i))
        if y>=X:
            q_append((y,i,i))
    
    test1=float("inf")
    rmq=SegTree(init_val,segfunc,ide_ele)
    q.sort()
    for i in range(len(q)):
        val,k,index=q[i]
        if k==-1:
            rmq.update(index,val)
        else:
            res=rmq.query(0,N)
            test1=min(val-res,test1)
    
    test2=(max(r)-min(r))*(max(b)-min(b))
    test1*=(max(max(b),max(r))-min(min(b),min(r)))
    print(min(test1,test2))

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = float("inf")
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys

input=sys.stdin.readline

N=int(input())
q=[]
init_val=[0]*N
ball=[]
X=0
for i in range(N):
    x,y=map(int,input().split())
    q.append((x,i,i))
    q.append((y,i,i))
    init_val[i]=min(x,y)
    q.append((max(x,y),-1,i))
    ball.append((x,y))
    X=max(X,min(x,y))

test1=float("inf")
rmq=SegTree(init_val,segfunc,ide_ele)
q.sort()
for i in range(len(q)):
    val,k,index=q[i]
    if k==-1:
        rmq.update(index,val)
    else:
        res=rmq.query(0,N)
        if val-X>=0:
            test1=min(val-res,test1)

test2=0
r=[]
b=[]
for i in range(N):
    x,y=ball[i]
    if x>y:
        r.append(x)
        b.append(y)
    else:
        r.append(y)
        b.append(x)

test2=(max(r)-min(r))*(max(b)-min(b))
test1*=(max(max(b),max(r))-min(min(b),min(r)))
print(min(test1,test2))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
  l[i].sort()

ans=[]
l.sort()
B1=[];R1=[]
for i in range(n):
  B1.append(max(l[i]))
  R1.append(min(l[i]))
ans.append((max(B1)-min(B1))*(max(R1)-min(R1)))

Bleft=[]
Bright=[]
Rleft=[]
Rright=[]

M=B1[0];m=B1[0]
Bleft.append([m,M])
for i in range(1,n):
  M=max(M,B1[i])
  m=min(m,B1[i])
  Bleft.append([m,M])

B1.reverse()
M=B1[0];m=B1[0]
Bright.append([m,M])
for i in range(1,n):
  M=max(M,B1[i])
  m=min(m,B1[i])
  Bright.append([m,M])

M=R1[0];m=R1[0]
Rleft.append([m,M])
for i in range(1,n):
  M=max(M,R1[i])
  m=min(m,R1[i])
  Rleft.append([m,M])

R1.reverse()
M=R1[0];m=R1[0]
Rright.append([m,M])
for i in range(1,n):
  M=max(M,R1[i])
  m=min(m,R1[i])
  Rright.append([m,M])

for i in range(n-1):
  M1=max(Bleft[i][1],Rright[n-2-i][1])
  m1=min(Bleft[i][0],Rright[n-2-i][0])
  M2=max(Rleft[i][1],Bright[n-2-i][1])
  m2=min(Rleft[i][0],Bright[n-2-i][0])
  ans.append((M1-m1)*(M2-m2))

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc073/tasks/arc073_c

全体の最大値と、最小値は必ず4つ中に含まれる
最大を必ず赤に割り振るとする

(1)最小が最大とペアでないとき、→自由な方における
(2)ペアの時、→青にしか置けない

ありうる分け方は2つ
(A)最小を赤にすると決めた時
    青の最大値を最小化して、最小値を最大化するのがよさそう？

(B)最小を青にするとき
    →赤の最小値を最大化、青の最大値を最小化するのが良い
    →貪欲に大きい方を赤&小さい方を青に選んでいけばよい

問題は(A)の時か…

青には、最小と最大の余り物は必ず含まれる。
また、残りのペアの内、最小値の最大 <= 青最大 　最大値の最小>=青最小
は必ず満たされる。


尺取り法！！
で、Nこのペアから1つづつ取るときの最大と最小の差の最小値を求められる

x>yにしておこう
"""
from collections import deque
N = int(input())

xy = []
maxind = 0
minind = 0

for i in range(N):

    x,y = map(int,input().split())
    if x < y:
        t = x
        x = y
        y = t

    xy.append([x,y])
        
    if x > xy[maxind][0]:
        maxind = i
    if y < xy[minind][1]:
        minind = i

rmin = float("inf")
bmax = float("-inf")

for i in range(N): #最大と最小が別サイドの場合(貪欲)

    x,y = xy[i]

    if i == maxind and i == minind:
        continue
    elif i == maxind:
        bmax = max(bmax,y)
        continue
    elif i == minind:
        rmin = min(rmin,x)
        continue
    
    rmin = min(rmin,max(x,y))
    bmax = max(bmax,min(x,y))


ans = (xy[maxind][0] - rmin) * (bmax - xy[minind][1])
#print (ans)

if maxind != minind: #最大と最小を同じサイドに置く場合(尺取り法)
    
    side_R = xy[maxind][0] - xy[minind][1]

    apnum = 0
    aplis = [0] * N

    wait = []

    for i in range(N):

        if i == maxind:
            wait.append([xy[i][1],i])
        elif i == minind:
            wait.append([xy[i][0],i])
        else:
            wait.append([xy[i][0],i])
            wait.append([xy[i][1],i])

    q = deque([])
    wait.sort()

    for num,ind in wait:

        if aplis[ind] == 0:
            apnum += 1
        aplis[ind] += 1
        q.append([num,ind])

        if apnum == N:

            while len(q) > 0 and aplis[q[0][1]] > 1:
                pn,pi = q.popleft()
                aplis[pi] -= 1

            ans = min(ans, side_R * (q[-1][0] - q[0][0]))

print (ans)

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc073/tasks/arc073_c

全体の最大値と、最小値は必ず4つ中に含まれる
最大を必ず赤に割り振るとする

(1)最小が最大とペアでないとき、→自由な方における
(2)ペアの時、→青にしか置けない

ありうる分け方は2つ
(A)最小を赤にすると決めた時
    青の最大値を最小化して、最小値を最大化するのがよさそう？

(B)最小を青にするとき
    →赤の最小値を最大化、青の最大値を最小化するのが良い
    →貪欲に大きい方を赤&小さい方を青に選んでいけばよい

問題は(A)の時か…

青には、最小と最大の余り物は必ず含まれる。
また、残りのペアの内、最小値の最大 <= 青最大 　最大値の最小>=青最小
は必ず満たされる。


尺取り法！！
で、Nこのペアから1つづつ取るときの最大と最小の差の最小値を求められる

x>yにしておこう
"""
from collections import deque
N = int(input())

xy = []
maxind = 0
minind = 0

for i in range(N):

    x,y = map(int,input().split())
    if x < y:
        t = x
        x = y
        y = t

    xy.append([x,y])
        
    if x > xy[maxind][0]:
        maxind = i
    if y < xy[minind][1]:
        minind = i

rmin = float("inf")
bmax = float("-inf")

for i in range(N): #最大と最小が別サイドの場合(貪欲)

    x,y = xy[i]

    if i == maxind and i == minind:
        continue
    elif i == maxind:
        bmax = max(bmax,y)
        continue
    elif i == minind:
        rmin = min(rmin,x)
        continue
    
    rmin = min(rmin,max(x,y))
    bmax = max(bmax,min(x,y))


ans = (xy[maxind][0] - rmin) * (bmax - xy[minind][1])
#print (ans)

if maxind != minind: #最大と最小を同じサイドに置く場合(尺取り法)
    
    side_R = xy[maxind][0] - xy[minind][1]

    apnum = 0
    aplis = [0] * N

    wait = []

    for i in range(N):

        if i == maxind:
            wait.append([xy[i][1],i])
        if i == minind:
            wait.append([xy[i][0],i])
        else:
            wait.append([xy[i][0],i])
            wait.append([xy[i][1],i])

    q = deque([])
    wait.sort()

    for num,ind in wait:

        if aplis[ind] == 0:
            apnum += 1
        aplis[ind] += 1
        q.append([num,ind])

        if apnum == N:

            while len(q) > 0 and aplis[q[0][1]] > 1:
                pn,pi = q.popleft()
                aplis[pi] -= 1

            ans = min(ans, side_R * (q[-1][0] - q[0][0]))

print (ans)

Submission status: Time Limit Exceeded

Solution code:
def solve1():
	maxx = maxy = 0
	minx = miny = 1000111000
	for i in xrange(n):
		maxx = max(maxx, x[i])
		minx = min(minx, x[i])
		maxy = max(maxy, y[i])
		miny = min(miny, y[i])
	return (maxx-minx)*(maxy-miny)

def solve2a(minx):
	miny = min(x)
	maxy = max(y)
	maxx = 0
	
	for i in xrange(n):
		if y[i] < minx:
			return 2**60
		if minx <= x[i]:
			maxx = max(maxx, x[i])
		else:
			maxx = max(maxx, y[i])
	return (maxx-minx)*(maxy-miny)

def solve2():
	res = 2**60
	for minx in x:
		res = min(res, solve2a(minx))
	for minx in y:
		res = min(res, solve2a(minx))
	return res

n = int(raw_input())

x = [0]*n
y = [0]*n
mini = maxi = 0
for i in xrange(n):
	x[i],y[i] = map(int, raw_input().split())
	x[i],y[i] = min(x[i],y[i]),max(x[i],y[i])
	if x[i] < x[mini]:
		mini = i
	if y[maxi] < y[i]:
		maxi = i

ans = solve1()
if mini != maxi:
	ans = min(ans, solve2())
print ans

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
N = int(input())

Rmax = 0
Rmin = 1000000001
Bmax = 0
Bmin = 1000000001

data = sorted([sorted(list(map(int, input().split()))) for i in range(N)],key=lambda x:x[0])

def target(data):
    tempBlues = sorted([d[0] for d in data])
    tempReds = sorted([d[1] for d in data])
    return (max(tempBlues) - min(tempBlues))*(max(tempReds) - min(tempReds))


minValue = target(data)

for i in range(N):
    data[i] = [data[i][1],data[i][0]]
    tempValue = target(data)
    if tempValue < minValue:
        minValue = tempValue
    
print(minValue)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from random import *
from functools import reduce,partial
from time import time
from pprint import pprint

def readln():
    return list(map(int,input().split(' ')))

def identity(x):
    """Return the input itself."""
    return x

def constant(c):
    """Return an function which always
    returns the input constant c."""
    def const_function(const,*args):
        return const
    return partial(const_function,c)

def inc(c = 1):
    """Return a function which reads an input x and returns x + c as output.
    By default, c equals 1."""
    return lambda x: x + c

def add(*args):
    """Return the sum of the input."""
    def add2(x,y): return x + y
    return reduce(add2,args)

def mapv(f,*lst):
    """Return a vector of the result of map."""
    return list(map(f,*lst))

def vector(*args):
    """Return a vector of input parameters."""
    return args

def sequence(n,f = constant(0)):
    """Return a vector of length n, and initialize the i'th
    item with f(i).By default the vector will initialized with 0."""
    return [f(i) for i in range(0,n)]

def matrix(n,m,f = constant(0)):
    """Return a 2-dim vector which contains n vectors with length m.
    The j's item of vector i will be initialized by f(i,j).By default,
    the vector will be initialized with 0."""
    return [[f(i,j) for j in range(0,m)] for i in range(0,n)]

def flat(v):
    """Return a flat vector which contains the elements of v in their
    origin order.If the input is not a vector, return a vector which
    only contains the input."""
    if not isinstance(v,list): return [v]
    if not v: return []
    return reduce(add,mapv(flat,v))

def partition(v,f = identity):
    """Partition vector v by f(v[i]).
    e.g. partition([1,2,3,1,2,3],identity()) == {1:[1,1,1], 2:[2,2], 3:[3]}
    By default, the vector will be partitioned by identity function."""
    result = {}
    for item in v:
        key = f(item)
        s = result.get(key)
        if s:
            s.append(item)
        else:
            result.update({key:[item]})
    return result

def getValue(key):
    """Return a function which returns the value of key in a hash-map.
    If the key do not exist, it will throw an error."""
    return lambda x: x[key]

def mapValue(f,m):
    """Replace each value in hash-map m with f(value).
    Return the new hash-map."""
    res = {}
    for key in m:
        res.update({key: f(m[key])})
    return res

p = 1000000000 + 7

n = readln()[0]
a = []
for i in range(0,n):
    a.append(sorted(readln()))
a = sorted(a)
up = [row[:] for row in a]
down = [row[:] for row in a]
for i in range(1,n):
    up[i] = mapv(max,up[i-1],a[i])
    down[i] = mapv(min,down[i-1],a[i])
ans = (up[n-1][0] - down[n-1][0]) * (up[n-1][1] - down[n-1][1])
u = a[n-1]
d = a[n-1]
for i in range(1,n):
    index = n - 1 - i
    u = mapv(max,u,a[index])
    d = mapv(min,d,a[index])
    x = max(u[0],up[index - 1][1]) - min(d[0],down[index - 1][1])
    y = max(u[1],up[index - 1][0]) - min(d[1],down[index - 1][0])
    ans = min(ans,x*y)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.
    If x is already in a, insert it to the right of the rightmost x.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)
insort=insort_right

n=int(input())
x,y,p=[],[],[]
for i in range(n):
    a,b=map(int,input().split())
    if a > b: a,b=b,a
    x.append(a)
    y.append(b)
    p.append((a,i,True))
    p.append((b,i,False))
p.sort()
ans=(max(x)-min(x))*(max(y)-min(y))
if p[0][1] != p[-1][1]:
    a=p[-1][0] - p[0][0]
    bs=[]
    bs.append((y[p[0][1]] if p[0][2] else x[p[0][1]], p[0][1]))
    bs.append((y[p[-1][1]] if p[-1][2] else x[p[-1][1]], p[-1][1]))
    for i in range(n):
        if i in (p[0][1], p[-1][1]):
            continue
        bs.append((x[i],i))
    bs.sort()
    b=bs[-1][0]-bs[0][0]
    for i in range(n):
        if bs[0][1] in (p[0][1], p[-1][1]):
            break
        if y[bs[0][1]] == bs[0][0]:
            break
        v,j=bs.pop(0)
        insort(bs,(y[j],j))
        b=min(b, bs[-1][0]-bs[0][0])
    ans=min(ans, a*b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, nlargest, nsmallest

n=int(input())
x,y,p=[],[],[]
for i in range(n):
    a,b=map(int,input().split())
    if a > b: a,b=b,a
    x.append(a)
    y.append(b)
    p.append((a,i,True))
    p.append((b,i,False))
p.sort()
ans=(max(x)-min(x))*(max(y)-min(y))
if p[0][1] != p[-1][1]:
    a=p[-1][0] - p[0][0]
    bs=[]
    heappush(bs, (y[p[0][1]] if p[0][2] else x[p[0][1]], p[0][1]))
    heappush(bs, (y[p[-1][1]] if p[-1][2] else x[p[-1][1]], p[-1][1]))
    for i in range(n):
        if i in (p[0][1], p[-1][1]):
            continue
        heappush(bs, (x[i],i))
    b=nlargest(1, bs)[0][0]-nsmallest(1, bs)[0][0]
    for i in range(n):
        sm=nsmallest(1, bs)[0]
        if sm[1] in (p[0][1], p[-1][1]):
            break
        if y[sm[1]] == sm[0]:
            break
        v,j=heappop(bs)
        heappush(bs,(y[j],j))
        b=min(b, nlargest(1, bs)[0][0]-nsmallest(1, bs)[0][0])
    ans=min(ans, a*b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort

n=int(input())
x,y,p=[0]*n,[0]*n,[0]*(2*n)
for i in range(n):
    a,b=map(int,input().split())
    if a > b: a,b=b,a
    x[i] = a
    y[i] = b
    p[i*2] = (a,i,True)
    p[i*2+1] = (b,i,False)
p.sort()
x_=sorted(x)
y_=sorted(y)
ans=((x_[-1]-x_[0])*(y_[-1]-y_[0]))
if p[0][1] != p[-1][1]:
    a=p[-1][0] - p[0][0]
    bs=[(x[i],i) for i in range(n)]
    bs[p[0][1]] = (y[p[0][1]] if p[0][2] else x[p[0][1]], p[0][1])
    bs[p[-1][1]] = (y[p[-1][1]] if p[-1][2] else x[p[-1][1]], p[-1][1])
    bs.sort()
    b=bs[-1][0]-bs[0][0]
    for i in range(n):
        if bs[0][1] in (p[0][1], p[-1][1]):
            break
        if y[bs[0][1]] == bs[0][0]:
            break
        v,j=bs.pop(0)
        insort(bs,(y[j],j))
        b=min(b, bs[-1][0]-bs[0][0])
    ans=min(ans, a*b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort

n=int(input())
x,y,p=[],[],[]
for i in range(n):
    a,b=map(int,input().split())
    if a > b: a,b=b,a
    x.append(a)
    y.append(b)
    p.append((a,i,True))
    p.append((b,i,False))
p.sort()
ans=(max(x)-min(x))*(max(y)-min(y))
if p[0][1] != p[-1][1]:
    a=p[-1][0] - p[0][0]
    bs=[]
    bs.append((y[p[0][1]] if p[0][2] else x[p[0][1]], p[0][1]))
    bs.append((y[p[-1][1]] if p[-1][2] else x[p[-1][1]], p[-1][1]))
    for i in range(n):
        if i in (p[0][1], p[-1][1]):
            continue
        bs.append((x[i],i))
    bs.sort()
    b=bs[-1][0]-bs[0][0]
    for i in range(n):
        if bs[0][1] in (p[0][1], p[-1][1]):
            break
        if y[bs[0][1]] == bs[0][0]:
            break
        v,j=bs.pop(0)
        insort(bs,(y[j],j))
        b=min(b, bs[-1][0]-bs[0][0])
    ans=min(ans, a*b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    n = I()
    a = sorted([sorted(LI()) + [_] for _ in range(n)])
    b = sorted(a, key=lambda x: x[1])
    r = (a[-1][0]-a[0][0]) * (b[-1][1]-b[0][1])
 
 
    bm = b[-1][1] - a[0][0]
    bmi = b[0][2]
    am = a[-1][1]
    at = 0
    k = [[inf,0]]
    for i in range(n-1):
        kk = []
        kk.append(min(k[-1][0], b[i][0], b[i+1][1]))
        kk.append(max(k[-1][1], b[i][0]))
        if kk[0] == k[-1][0]:
            k[-1][1] = kk[1]
        else:
            k.append(kk)
 
    k = k[1:]
    kl = len(k)
 
    am = b[-1][1] - a[0][0]
    ami = a[0][2]
    bm = 0
    mtm = 0
    bt = b[0][1]
 
    for i in range(n-1,0,-1):
        tm = b[i][0]
        if mtm < tm:
            mtm = tm
        if ami == b[i][2]:
            break
        if tm < bt:
            bt = tm
        if tm < b[i-1][1]:
            tm = b[i-1][1]
        bm = mtm
        if tm > bm:
            bm = tm
 
        tr = am * (bm-bt)
        if r > tr:
            r = tr
 
        for j in range(kl):
            ki,km = k[j]
            if km > bm:
                break
            tr = am * (bm-min(ki,bt))
            if r > tr:
                r = tr
 
    return r
 
 
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    if n == 1:
        return 0
    a = sorted([sorted(LI()) + [_] for _ in range(n)])
    b = sorted(a, key=lambda x: x[1])
    r = (a[-1][0]-a[0][0]) * (b[-1][1]-b[0][1])


    bm = b[-1][1] - a[0][0]
    bmi = b[0][2]
    am = a[-1][1]
    at = 0
    k = [[inf,0]]
    for i in range(n-1):
        kk = []
        kk.append(min(k[-1][0], b[i][0], b[i+1][1]))
        kk.append(max(k[-1][1], b[i][0]))
        if kk[0] == k[-1][0]:
            k[-1][1] = kk[1]
        else:
            k.append(kk)

    k = k[1:]
    kl = len(k)

    am = b[-1][1] - a[0][0]
    ami = a[0][2]
    bm = 0
    mtm = 0
    bt = b[0][1]

    for i in range(n-1,0,-1):
        tm = b[i][0]
        if mtm < tm:
            mtm = tm
        if ami == b[i][2]:
            break
        if tm < bt:
            bt = tm
        if tm < b[i-1][1]:
            tm = b[i-1][1]
        bm = mtm
        if tm > bm:
            bm = tm

        tr = am * (bm-bt)
        if r > tr:
            r = tr

        for j in range(kl):
            ki,km = k[j]
            tr = am * (max(km,bm)-min(ki,bt))
            if r > tr:
                r = tr
            if km >= bm:
                break

    return r


print(main())

Submission status: Accepted

Solution code:
n = int(input())
lis = []
a, b = [], []
for i in range(n):
    X, Y = map(int, input().split())
    lis.append([min(X, Y), max(X, Y)])
    a.append(min(X, Y))
    b.append(max(X, Y))
lis.sort()
answer = (max(a) - min(a)) * (max(b) - min(b))
a_max, b_min = max(a), min(b)
current = float("inf")
for i in range(n):
    if lis[i][0] > b_min:
        current = min(current, a_max - b_min)
        break
    current = min(current, a_max - lis[i][0])
    a_max = max(a_max, lis[i][1])
print(min(answer, current * (max(b) - min(a))))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
xy = list(map(int,read().split()))

if(n==1):
    print(0)
    exit()

max_num = max(xy)
min_num = min(xy)

max_ind = -1
min_ind = -1
same = False
big = []
small = []
for i in range(n):
    x,y = xy[i*2:i*2+2]
    if(x>y):
        x,y = y,x

    if(x==min_num)&(y==max_num):
        same = True

    if(x==min_num):
        min_ind = i
    if(y==max_num):
        max_ind = i

    big.append(y)
    small.append(x)

#最大と最小を違う色に塗る
ans = (max(big)-min(big)) * (max(small) - min(small))
if(same):
    print(ans)
    exit()

#同じ色に塗る
r = max_num - min_num
if(xy[min_ind*2]==min_num):
    min_pair = xy[min_ind*2+1]
else:
    min_pair = xy[min_ind*2]

if(xy[max_ind*2]==max_num):
    max_pair = xy[max_ind*2+1]
else:
    max_pair = xy[max_ind*2]

nums = []
for i in range(n):
    if(i==min_ind)|(i==max_ind):
        continue
    x,y = xy[i*2:i*2+2]

    nums.append((x,i))
    nums.append((y,i))

nums.append((min_pair,min_ind))
nums.append((max_pair,max_ind))

nums.sort()

set0 = set(range(n))
set1 = set()
set2 = set()

left = 0
right = 0
while(right <= len(nums)):
    if(not set0):
        b = nums[right-1][0] - nums[left][0]
        ans = min(ans,r*b)

        l_ind = nums[left][1]
        if(l_ind in set2):
            set2.remove(l_ind)
            set1.add(l_ind)
        else:
            set1.remove(l_ind)
            set0.add(l_ind)

        left += 1

    else:
        if(right==len(nums)):
            break
        r_ind = nums[right][1]
        if(r_ind in set1):
            set1.remove(r_ind)
            set2.add(r_ind)
        else:
            set0.remove(r_ind)
            set1.add(r_ind)
        right += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,readline().split())

xy = []
for _ in range(n):
    x,y = map(int,readline().split())
    if x>y: x,y = y,x
    xy.append((x,y))
xy.sort()


xx = []
yy = []
for x,y in xy:
    xx.append(x)
    yy.append(y)


ymaxr = yy[:]
for i in range(n-2,-1,-1):
    ymaxr[i] = max(ymaxr[i],ymaxr[i+1])

ymaxl= yy[:]
for i in range(1,n):
    ymaxl[i] = max(ymaxl[i],ymaxl[i-1])

ymin = yy[:]
for i in range(1,n):
    ymin[i] = min(ymin[i],ymin[i-1])

#print(yy)
#print(ymaxl)
#print(ymaxr)
#print(ymin)

#print(xx,yy)

ans = 1<<60
for i in range(n):
    mr = xx[0]

    Mr = xx[i]
    if i != n-1: Mr = max(Mr,ymaxr[i+1])
    
    mb = ymin[i]
    if i != n-1: mb = min(mb,xx[i+1])
    
    Mb = ymaxl[i]
    if i != n-1: Mb = max(Mb,xx[n-1])

    #print(i,mr,Mr,mb,Mb)
        
    ans = min(ans,(Mr-mr)*(Mb-mb))


print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
L, R = [], []
LR = []
INF = 10**9+1
m, M = INF, 0
for i in range(n):
  x, y = map(int, input().split())
  if x > y:
    x, y = y, x
  L.append(x)
  R.append(y)
  LR.append((x, y))
  if m > x:
    m = x
    idx_m = i
  if M < y:
    M = y
    idx_M = i
ans1 = (M-min(R))*(max(L)-m)
if idx_m == idx_M:
  print(ans1)
  exit()
a, b = L[idx_M], R[idx_m]
if a > b:
  a, b = b, a
LR = sorted([lr for i, lr in enumerate(LR) if i != idx_m and i != idx_M])
if not LR:
  print(ans1)
  exit()
L, R = zip(*LR)
max_R = [-1]*(n-2)
min_R = [-1]*(n-2)
max_R[0] = R[0]
min_R[0] = R[0]
for i in range(n-3):
  max_R[i+1] = max(max_R[i], R[i+1])
  min_R[i+1] = min(min_R[i], R[i+1])
l_min, l_max = L[0], L[-1]
ans2 = max(b, l_max) - min(a, l_min)
for i in range(n-2):
  if i < n-3:
    l_min = min(min_R[i], L[i+1])
  else:
    l_min = min_R[i]
  l_max = max(l_max, max_R[i])
  ans2 = min(ans2, max(b, l_max) - min(a, l_min))
ans2 *= M-m
ans = min(ans1, ans2)
print(ans)

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = float("inf")
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import sys,random

    input=sys.stdin.readline

    N=int(input())
    q=[]
    r=[]
    b=[]
    X=0
    q_append=q.append
    for i in range(N):
        x,y=map(int,input().split())
        r.append(max(x,y))
        b.append(min(x,y))


    X=max(b)
    init_val=[b[i] for i in range(N)]
    for i in range(N):
        x,y=r[i],b[i]
        if X>r[i]:
            init_val[i]=r[i]
        elif X>b[i]:
            q_append((r[i],i,-1))
            init_val[i]=b[i]
        else:
            q_append((b[i],i,1))
            q_append((r[i],i,-1))
            init_val[i]=b[i]

    q.sort()
    test1=float("inf")
    rmq=SegTree(init_val,segfunc,ide_ele)
    

    for i in range(0,len(q)):
        val,index,k=q[i]
        if k==-1:
            rmq.update(index,val)
        res=rmq.query(0,N)
        test1=min(val-res,test1)


    test2=(max(r)-min(r))*(max(b)-min(b))
    test1*=(max(max(b),max(r))-min(min(b),min(r)))
    print(min(test1,test2))

if __name__=="__main__":
    main()