Problem:
 Score : 700 points    Problem Statement Takahashi and Aoki will play a game with a number line and some segments.
Takahashi is standing on the number line and he is initially at coordinate 0 .
Aoki has N segments. The i -th segment is [L_i,R_i] , that is, a segment consisting of points with coordinates between L_i and R_i (inclusive).  The game has N steps. The i -th step proceeds as follows:   First, Aoki chooses a segment that is still not chosen yet from the N segments and tells it to Takahashi.  Then, Takahashi walks along the number line to some point within the segment chosen by Aoki this time.   After N steps are performed, Takahashi will return to coordinate 0 and the game ends.  Let K be the total distance traveled by Takahashi throughout the game. Aoki will choose segments so that K will be as large as possible, and Takahashi walks along the line so that K will be as small as possible. What will be the value of K in the end?      Constraints  1 ≤ N ≤ 10^5  -10^5 ≤ L_i < R_i ≤ 10^5  L_i and R_i are integers.         Input Input is given from Standard Input in the following format:  N  L_1  R_1 : L_N  R_N       Output Print the total distance traveled by Takahashi throughout the game when Takahashi and Aoki acts as above.
It is guaranteed that K is always an integer when L_i,R_i are integers.        Sample Input 1 3
-5 1
3 7
-4 -2      Sample Output 1 10  One possible sequence of actions of Takahashi and Aoki is as follows:   Aoki chooses the first segment. Takahashi moves from coordinate 0 to -4 , covering a distance of 4 .  Aoki chooses the third segment. Takahashi stays at coordinate -4 .  Aoki chooses the second segment. Takahashi moves from coordinate -4 to 3 , covering a distance of 7 .  Takahashi moves from coordinate 3 to 0 , covering a distance of 3 .   The distance covered by Takahashi here is 14 (because Takahashi didn't move optimally).
It turns out that if both players move optimally, the distance covered by Takahashi will be 10 .       Sample Input 2 3
1 2
3 4
5 6      Sample Output 2 12       Sample Input 3 5
-2 0
-2 0
7 8
9 10
-2 -1      Sample Output 3 34

Solution (Python):
I,i,H=input,int,range
n,L,R,A,C=i(I()),[0],[0],0,0
for _ in H(n):l,r=map(i,I().split());L+=[l];R+=[r]
L=sorted(L)[::-1];R.sort()
for j in H(n):C+=(L[j]-R[j])*2;A=max(A,C)
print(A)

Solution (Python):
I,i,H=input,int,range
n,L,R,A,C=i(I()),[0],[0],0,0
for _ in H(n):l,r=map(i,I().split());L+=[l];R+=[r]
L=sorted(L)[::-1];R.sort()
for j in H(n//2+1):C+=(L[j]-R[j])*2;A=max(A,C)
print(A)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = []
l = [i for i in range(N)]
r = [i for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  a.append((x, y))
l.sort(key = lambda x: -a[x][1])
r.sort(key = lambda x: a[x][0])

res = 0
vis = [0] * N
x = 0
for i in range(N):
  
  if i % 2 == 1 and (len(l) > 0):
    t = l[-1]
    y = a[l.pop()][1]
    while vis[t]:
      t = l.pop()
      y = a[t][1]
      vis[t] = 1
      if len(l) == 0: break
    vis[t] = 1
    if not x in range(a[t][0], a[t][1]):
      res += x - min(x, y)
      x = min(x, y)
  elif i % 2 == 0 and (len(r) > 0):
    t = r[-1]
    y = a[r.pop()][0]
    while vis[t]:
      t = r.pop()
      y = a[t][0]
      vis[t] = 1
      if len(r) == 0: break
    vis[t] = 1
    if not x in range(a[t][0], a[t][1]):
      res += max(x, y) - x
      x = max(x, y)
res += abs(x)

rres = 0
l = [i for i in range(N)]
r = [i for i in range(N)]
l.sort(key = lambda x: -a[x][1])
r.sort(key = lambda x: a[x][0])
vis = [0] * N
x = 0
for i in range(N):
  
  if i % 2 == 0 and (len(l) > 0):
    t = l[-1]
    y = a[l.pop()][1]
    while vis[t]:
      t = l.pop()
      y = a[t][1]
      vis[t] = 1
      if len(l) == 0: break
    vis[t] = 1
    if not x in range(a[t][0], a[t][1]):
      rres += x - min(x, y)
      x = min(x, y)
  elif i % 2 == 1 and (len(r) > 0):
    t = r[-1]
    y = a[r.pop()][0]
    while vis[t]:
      t = r.pop()
      y = a[t][0]
      vis[t] = 1
      if len(r) == 0: break
    vis[t] = 1
    if not x in range(a[t][0], a[t][1]):
      rres += max(x, y) - x
      x = max(x, y)
rres += abs(x)
print(max(res, rres))

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    
    mod = 1000000007
    

    N = int(input())
    
    
    
    S = tuple(tuple(map(int, input().split())) for i in range(N)) 
    base=N
    ls=[];rs=[]
    for i,(l,r) in enumerate(S):
        heappush(ls,-l*base+i)
        heappush(rs,r*base+i)
    
    dset=set()
    cur=0
    tot=0
    f=0
    lsc=ls.copy()
    rsc=rs.copy()
    while ls and rs:
        while ls:
            l,i=divmod(heappop(ls),base)
            l*=-1
            if i in dset:
                dset.remove(i)
            elif cur<l:
                tot+=l-cur
                dset.add(i)
                cur=l
                break
            else:
                f=1
                break
        if f:
            break
        while rs:
            r,i=divmod(heappop(rs),base)
            if i in dset:
                dset.remove(i)
            elif cur>r:
                tot+=cur-r
                cur=r
                dset.add(i)
                break
            else:
                f=1
                break
        if f:
            break
    tot+=abs(cur)

    ls=lsc
    rs=rsc
    dset=set()
    cur=0
    tot2=0
    f=0
    while ls and rs:
        while rs:
            r,i=divmod(heappop(rs),base)
            if i in dset:
                dset.remove(i)
            elif cur>r:
                tot2+=cur-r
                cur=r
                dset.add(i)
                break
            else:
                f=1
                break

        if f:
            break
        while ls:
            l,i=divmod(heappop(ls),base)
            l*=-1
            if i in dset:
                dset.remove(i)
            elif cur<l:
                tot2+=l-cur
                dset.add(i)
                cur=l
                break
            else:
                f=1
                break
            if f:
                break
    tot2+=abs(cur)

    print(max(tot,tot2))




if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
left = []
right = []
left_inv = []
right_inv = []
for i in range(N):
    L, R = map(int, input().split())
    left.append((R, i))
    right.append((L, i))
    left_inv.append((-L, i))
    right_inv.append((-R, i))

def calc(left, right):
    left.sort(key=lambda p: -p[0])
    right.sort(key=lambda p: p[0])
    used = set()
    x = 0
    ans = 0
    while right or left:
        while right and right[-1][1] in used:
            right.pop()
        if right:
            y, i = right.pop()
            used.add(i)
            if x < y:
                ans += y - x
                x = y
        while left and left[-1][1] in used:
            left.pop()
        if left:
            y, i = left.pop()
            used.add(i)
            if y < x:
                ans += x - y
                x = y
    ans += abs(x)
    return ans

ans = max(calc(left, right), calc(left_inv, right_inv))
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint
from copy import deepcopy


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n = I()
L = []
for i in range(n):
    l, r = LI()
    L += [(l, r, i)]

A = sorted(L, reverse=True)
B = sorted(L, key=lambda x:x[1])
used = [0] * n
now = 0
b_idx = 0
a_idx = 0
ans = 0
for i in range(n):
    if i % 2:
        while True:
            li, ri, idx = A[a_idx]
            if used[idx]:
                a_idx += 1
            else:
                used[idx] = 1
                break
        if li <= now <= ri:
            continue
        elif ri < now:
            ans += now - ri
            now = ri
        else:
            ans += li - now
            now = li
    else:
        while True:
            li, ri, idx = B[b_idx]
            if used[idx]:
                b_idx += 1
            else:
                used[idx] = 1
                break
        if li <= now <= ri:
            continue
        elif now < li:
            ans += li - now
            now = li
        else:
            ans += now - ri
            now = ri
ans += abs(now)
used = [0] * n
now = 0
ans1 = ans
b_idx = 0
a_idx = 0
ans2 = 0
for i in range(n):
    if i % 2 == 0:
        while True:
            li, ri, idx = A[a_idx]
            if used[idx]:
                a_idx += 1
            else:
                used[idx] = 1
                break
        if li <= now <= ri:
            continue
        elif ri < now:
            ans2 += now - ri
            now = ri
        else:
            ans2 += li - now
            now = li
    else:
        while True:
            li, ri, idx = B[b_idx]
            if used[idx]:
                b_idx += 1
            else:
                used[idx] = 1
                break
        if li <= now <= ri:
            continue
        elif now < li:
            ans2 += li - now
            now = li
        else:
            ans2 += now - ri
            now = ri
ans2 += abs(now)

print(max(ans1, ans2))

Solution (Python):

def main():
    n = int(input())
    L, R = [0], [0]
    for i in range(n):
        l, r = map(int, input().split())
        L.append(l)
        R.append(r)
    L.sort()
    L.reverse()
    R.sort()

    res = 0
    for i in range(n + 1):
        if L[i] > R[i]:
            res += 2 * (L[i] - R[i])

    print(res)
if __name__ == '__main__':
    main()

Solution (Python):

import numpy as np

def main():
    n = int(input())
    L, R = [], []
    for i in range(n):
        l, r = map(int, input().split())
        L.append(l)
        R.append(r)
    ll = np.array(L); ll.sort(); ll = ll[::-1]
    rr = np.array(R); rr.sort()

    lll = ll.cumsum()
    rrr = rr.cumsum()

    x = (lll - rrr).max()
    y = (lll[1:] - rrr[:-1]).max()
    z = (lll[:-1] - rrr[1:]).max()

    print(2 * max(x, y, z))
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush
from copy import deepcopy

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


hq_left = []
hq_right = []

for i in range(n):
    l,r = lr[i*2:i*2+2]
    heappush(hq_left,(-1*l,i))
    heappush(hq_right,(r,i))

hq_left_origin = deepcopy(hq_left)
hq_right_origin = deepcopy(hq_right)

done = [0] * n
ans = -1*10**5
now = 10**5
while(len(hq_left)>0)&(len(hq_right)>0):
    while(hq_left):
        l,ind_l = hq_left[0]
        l *= -1
        if(done[ind_l] == 1):
            heappop(hq_left)
        else:
            break
    else:
        break

    while(hq_right):
        r,ind_r = hq_right[0]
        if(done[ind_r] == 1):
            heappop(hq_right)
        else:
            break
    else:
        break

    if( l-now > now-r):
        if(l > now):
            ans += l-now
            now = l
        done[ind_l] = 1
        heappop(hq_left)
    else:
        if(now > r):
            ans += now-r
            now = r
        done[ind_r] = 1
        heappop(hq_right)

ans += abs(now)

ans2 = -1*10**5
now = -1 * 10**5
hq_left = deepcopy(hq_left_origin)
hq_right = deepcopy(hq_right_origin)
done = [0] * n

while(len(hq_left)>0)&(len(hq_right)>0):
    while(hq_left):
        l,ind_l = hq_left[0]
        l *= -1
        if(done[ind_l] == 1):
            heappop(hq_left)
        else:
            break
    else:
        break

    while(hq_right):
        r,ind_r = hq_right[0]
        if(done[ind_r] == 1):
            heappop(hq_right)
        else:
            break
    else:
        break

    if( l-now > now-r):
        if(l > now):
            ans2 += l-now
            now = l
        done[ind_l] = 1
        heappop(hq_left)
    else:
        if(now > r):
            ans2 += now-r
            now = r
        done[ind_r] = 1
        heappop(hq_right)

ans2 += abs(now)


print(max(ans,ans2))

Solution (Python):
N, *LR = map(int, open(0).read().split())
L, R = LR[::2], LR[1::2]

L.sort(reverse=True)
R.sort()

ans = 0
cur = 0
for l, r in zip(L, R):
    ans = max(ans, cur + l, cur - r, cur + l - r)
    cur += l - r

print(2 * ans)

Solution (Python):
import heapq

N=int(input())
rque=[]
rque2=[]
lque=[]
lque2=[]
for i in range(N):
    l,r=map(int,input().split())
    rque.append((-l,i))
    rque2.append((-l,i))
    lque.append((r,i))
    lque2.append((r,i))

heapq.heapify(rque)
heapq.heapify(lque)
used=set([])
pos=0
dir="R"
ans=0
check=set([i for i in range(N)])
while used!=check:
    if dir=="R":
        l,i=heapq.heappop(rque)
        while i in used:
            l,i=heapq.heappop(rque)
        l*=-1
        if l>=pos:
            ans+=(l-pos)
            pos=l
            used.add(i)
            dir="L"
        else:
            break
    else:
        r,i=heapq.heappop(lque)
        while i in used:
            r,i=heapq.heappop(lque)
        if pos>=r:
            ans+=(pos-r)
            pos=r
            used.add(i)
            dir="R"
        else:
            break

test1=ans+abs(pos)

heapq.heapify(rque2)
heapq.heapify(lque2)
used=set([])
pos=0
dir="L"
ans=0
check=set([i for i in range(N)])
while used!=check:
    if dir=="R":
        l,i=heapq.heappop(rque2)
        while i in used:
            l,i=heapq.heappop(rque2)
        l*=-1
        if l>=pos:
            ans+=(l-pos)
            pos=l
            used.add(i)
            dir="L"
        else:
            break
    else:
        r,i=heapq.heappop(lque2)
        while i in used:
            r,i=heapq.heappop(lque2)
        if pos>=r:
            ans+=(pos-r)
            pos=r
            used.add(i)
            dir="R"
        else:
            break

test2=ans+abs(pos)
print(max(test1,test2))

Solution (Python):
n = int(input())
h = [tuple(map(int, input().split())) for _ in range(n)]
h.sort(key = lambda x : x[1])
l = [0]*(n+1)
r = l[:]
for i in range(n):
  r[i+1] = r[i] + h[i][1]
h.sort(reverse=True)
for i in range(n):
  l[i+1] = l[i] + h[i][0]
ans = 0
for _j in (-1, 0, 1):
  for i in range(n):
    j = i + _j
    if i + j <= n and j >= 0:
      ans = max(ans, l[i] - r[j])
print(ans*2)

Solution (Python):
def main():
    import heapq
    n = int(input())
    ab = [tuple(map(int, input().split())) for _ in [0]*n]
    
    d = dict()
    for a, b in ab:
        d[(a, b)] = d.get((a, b), 0)+1
    left, right = [(b, a) for a, b in ab], [(-a, b) for a, b in ab]
    heapq.heapify(left)
    heapq.heapify(right)
    ans1 = 0
    now = 0
    for i in range(n):
        while left:
            a, b = heapq.heappop(left)
            a, b = b, a
            if d[(a, b)] > 0:
                d[(a, b)] -= 1
                if b < now:
                    ans1 += now-b
                    now = b
                elif now < a:
                    ans1 += a-now
                    now = a
                break
        while right:
            a, b = heapq.heappop(right)
            a, b = -a, b
            if d[(a, b)] > 0:
                d[(a, b)] -= 1
                if now < a:
                    ans1 += a-now
                    now = a
                elif b < now:
                    ans1 += now-b
                    now = b
                break
    ans1 += abs(now)
    
    d = dict()
    for a, b in ab:
        d[(a, b)] = d.get((a, b), 0)+1
    left, right = [(b, a) for a, b in ab], [(-a, b) for a, b in ab]
    heapq.heapify(left)
    heapq.heapify(right)
    ans2 = 0
    now = 0
    for i in range(n):
        while right:
            a, b = heapq.heappop(right)
            a, b = -a, b
            if d[(a, b)] > 0:
                d[(a, b)] -= 1
                if now < a:
                    ans2 += a-now
                    now = a
                elif b < now:
                    ans2 += now-b
                    now = b
                break
        while left:
            a, b = heapq.heappop(left)
            a, b = b, a
            if d[(a, b)] > 0:
                d[(a, b)] -= 1
                if b < now:
                    ans2 += now-b
                    now = b
                elif now < a:
                    ans2 += a-now
                    now = a
                break
    ans2 += abs(now)
    print(max(ans1, ans2))


main()

Solution (Python):
n = int(input())
L = [0]
R = [0]

for i in range(n):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)

L.sort(reverse = True)
R.sort()

ans = 0
tmp = 0

for i in range(n):
	if L[i] - R[i] > 0:
		ans += 2 * (L[i] - R[i])
	else:
		print(ans)
		break

Solution (Python):
N = int(input())
L, R = [], []
for _ in range(N):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

L = sorted(L)[::-1]
R = sorted(R)

def calc(k):
    pre = 0
    s = 0
    for i in range(N):
        a = max(pre, L[i//2]) if i % 2 == k else min(pre, R[i//2])
        s += abs(pre - a)
        pre = a
    return s + abs(pre)

print(max(calc(0), calc(1)))

Solution (Python):

N = int(input())

L = []
R = []

for i in range(N):
    l,r = map(int,input().split())
    L.append(2 * l)
    R.append(-2 * r)

L.sort()
R.sort()
L.reverse()
R.reverse()

ans = 0

now = 0
for i in range(N):
    now += L[i]
    ans = max(ans,now)
    now += R[i]
    ans = max(ans,now)

now = 0
for i in range(N):
    now += R[i]
    ans = max(ans,now)
    now += L[i]
    ans = max(ans,now)

print (ans)

Solution (Python):

"""

貪欲か？
今いる地点から左のRと右のLの数を比較
多い方の最遠点に行く→そのような点が無くなったら終了

証明は…
まず右のR,左のLは無意味→区間を無駄にするだけ
少ない方に行く→多い方の区間が無駄になる
近い点に行く→　ここがむずい
遠い区間が無駄になるのを防ぐため？

実装は？
多い方の処理→BITで左にあるRの数と右にあるLの数をlogNで
優先度付きキューで最小のRと最大のLを検出
10^5+1 を足して1 ～ 2*10^5 + 1の区間として扱う
初期・終了地点は　10^5+1

"""
import heapq

def bitadd(a,w,bit): 
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): 
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

N = int(input())

used = [False] * N
lq = []
rq = []
LR = []

LBIT = [0] * (2 * (10**5) + 10)
RBIT = [0] * (2 * (10**5) + 10)

for i in range(N):

    L,R = map(int,input().split())

    L += 10**5+1
    R += 10**5+1

    LR.append([L,R])
    
    heapq.heappush(lq,[-1 * L,i])
    heapq.heappush(rq,[R,i])

    bitadd(L,1,LBIT)
    bitadd(R,1,RBIT)


ans = 0
now = 10**5+1

for i in range(N):

    R_in_left  = bitsum(now-1,RBIT)
    L_in_right = N - i - bitsum(now,LBIT)
    

    if R_in_left >= L_in_right: 

        while len(rq) > 0 and used[ rq[0][1] ]:
            heapq.heappop(rq)

        if len(rq) == 0:
            break

        nexp,nexind = heapq.heappop(rq)
        pair = LR[nexind][0]

        bitadd(nexp,-1,RBIT)
        bitadd(pair,-1,LBIT)
        used[nexind] = True

        if nexp >= now:
            break

        ans += now - nexp
        now = nexp

    else:

        while len(lq) > 0 and used[ lq[0][1] ]:
            heapq.heappop(lq)

        if len(lq) == 0:
            break

        nexp,nexind = heapq.heappop(lq)
        nexp *= -1
        pair = LR[nexind][1]

        bitadd(nexp,-1,LBIT)
        bitadd(pair,-1,RBIT)
        used[nexind] = True

        if nexp <= now:
            break

        ans += nexp - now
        now = nexp

ans += abs(10**5+1 - now)

print (ans)

Solution (Python):
from operator import itemgetter


def solve(array1, array2):
    set_ = set()
    stand = 0
    pos1 = 0
    pos2 = 0
    ans = 0
    cnt = 0
    n = len(array1)
    while True:
        if cnt == n:
            break
        while True:
            if array1[pos1][0] in set_:
                pos1 += 1
            else:
                i, l, r = array1[pos1]
                set_.add(i)
                if l <= stand <= r:
                    pass
                elif r < stand:
                    ans += stand - r
                    stand = r
                else:
                    ans += l - stand
                    stand = l
                cnt += 1
                break
        if cnt == n:
            break
        while True:
            if array2[pos2][0] in set_:
                pos2 += 1
            else:
                i, l, r = array2[pos2]
                set_.add(i)
                if l <= stand <= r:
                    pass
                elif r < stand:
                    ans += stand - r
                    stand = r
                else:
                    ans += l - stand
                    stand = l
                cnt += 1
                break
    return ans + abs(stand)


n = int(input())
info = [tuple([i] + list(map(int, input().split()))) for i in range(n)]

info1 = sorted(info, key = itemgetter(1), reverse = True)
info2 = sorted(info, key = itemgetter(2), reverse = True)
info3 = sorted(info, key = itemgetter(1))
info4 = sorted(info, key = itemgetter(2))

ans = 0
ans = max(ans, solve(info1, info2))
ans = max(ans, solve(info1, info3))
ans = max(ans, solve(info1, info4))
ans = max(ans, solve(info2, info3))
ans = max(ans, solve(info1, info4))
ans = max(ans, solve(info3, info4))
ans = max(ans, solve(info1, info1))
ans = max(ans, solve(info2, info2))
ans = max(ans, solve(info3, info3))
ans = max(ans, solve(info4, info4))
ans = max(ans, solve(info2, info1))
ans = max(ans, solve(info3, info1))
ans = max(ans, solve(info4, info1))
ans = max(ans, solve(info3, info2))
ans = max(ans, solve(info4, info2))
ans = max(ans, solve(info4, info3))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
Ls = []
Rs = []
l0 = 0
r0 = 0
for i in range(N):
    l, r = map(int, input().split())
    Ls.append((l, i))
    Rs.append((r, i))
    if l > 0:
        l0 += 1
    if r < 0:
        r0 += 1

Ls.sort(reverse=True)
Rs.sort()

used = [False]*N
if l0 > r0:
    toright = True
else:
    toright = False 

l = 0
r = 0
ans = 0
now = 0
for _ in range(N):
    if toright:
        while True:
            nl, ind = Ls[l]
            if used[ind]:
                l += 1
            else:
                used[ind] = True
                break
        if nl-now > 0:
            ans += nl - now
            now = nl
        toright = False
    else:
        while True:
            nr, ind = Rs[r]
            if used[ind]:
                r += 1
            else:
                used[ind] = True
                break
        if now-nr > 0:
            ans += now-nr
            now = nr
        toright = True

ans += abs(now)

print(ans)

Solution (Python):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
L, R = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))
L = np.array(L, dtype=int)
R = np.array(R, dtype=int)

LI = L.argsort()[::-1]
RI = R.argsort()

used = np.zeros(N, dtype=bool)
a1 = 0
n = 0
l = 0
r = 0
while True:
    while l < N and used[LI[l]]:
        l += 1
    if l >= N:
        break
    a1 += max(n, L[LI[l]]) - n
    n = max(n, L[LI[l]])
    used[LI[l]] = True

    while r < N and used[RI[r]]:
        r += 1
    if r >= N:
        break
    a1 += n - min(n, R[RI[r]])
    n = min(n, R[RI[r]])
    used[RI[r]] = True
a1 += abs(n)

used = np.zeros(N, dtype=bool)
a2 = 0
n = 0
l = 0
r = 0
while True:
    while r < N and used[RI[r]]:
        r += 1
    if r >= N:
        break
    a2 += n - min(n, R[RI[r]])
    n = min(n, R[RI[r]])
    used[RI[r]] = True

    while l < N and used[LI[l]]:
        l += 1
    if l >= N:
        break
    a2 += max(n, L[LI[l]]) - n
    n = max(n, L[LI[l]])
    used[LI[l]] = True
a2 += abs(n)

print(max(a1, a2))

Solution (Python):
import sys
import heapq
import copy
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    pq_L = []
    pq_R = []
    for i in range(N):
        L, R = map(int, input().split())
        heapq.heappush(pq_L, (-L, i))
        heapq.heappush(pq_R, (R, i))
    pq_L2 = copy.deepcopy(pq_L)
    pq_R2 = copy.deepcopy(pq_R)

    ans1 = 0
    prev = 0
    used = [0] * N
    for i in range(N):
        if i % 2 == 0:
            while True:
                _x, j = heapq.heappop(pq_L)
                x = -_x
                if not used[j]:
                    used[j] = 1
                    break
            if prev < x:
                ans1 += x - prev
                prev = x
        else:
            while True:
                x, j = heapq.heappop(pq_R)
                if not used[j]:
                    used[j] = 1
                    break
            if prev > x:
                ans1 += prev - x
                prev = x

    ans1 += abs(prev)

    ans2 = 0
    prev = 0
    used = [0] * N
    for i in range(N):
        if i % 2 == 1:
            while True:
                _x, j = heapq.heappop(pq_L2)
                x = -_x
                if not used[j]:
                    used[j] = 1
                    break
            if prev < x:
                ans2 += x - prev
                prev = x
        else:
            while True:
                x, j = heapq.heappop(pq_R2)
                if not used[j]:
                    used[j] = 1
                    break
            if prev > x:
                ans2 += prev - x
                prev = x

    ans2 += abs(prev)

    print(max(ans1, ans2))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
L, R = [0], [0]
for i in range(N):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

L.sort(reverse=True)
R.sort()

ans = 0
tmp = 0
for i in range(N):
    if L[i] - R[i] > 0:
        ans += 2 * (L[i] - R[i])
    else:
        print(ans)
        break

Solution (Python):
import sys
input = sys.stdin.readline

import numpy as np

N = int(input())
L,R = np.array([input().split() for _ in range(N)],dtype=np.int64).T


L.sort(); L = L[::-1]
R.sort()
Lcum = L.cumsum()
Rcum = R.cumsum()

x = (Lcum - Rcum).max()
y = (Lcum[1:] - Rcum[:-1]).max()
z = (Lcum[:-1] - Rcum[1:]).max()
answer = 2*max(x,y,z)
print(answer)

Solution (Python):


from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
L = []
R = []
for loop in range(N):
    l1, r1 = map(int, raw_input().split())
    L += [l1]
    R += [r1]
L.sort(reverse = True)
R.sort()

ans = 0
if L[0] > 0:
    S = L[0]
    L_pre = L[0]
    posL = 1
    posR = 0
    while True:
        R_pre = R[posR]
        posR += 1
        if L_pre < R_pre:
            S += abs(L_pre)
            break
        S += L_pre - R_pre
        L_pre = L[posL]
        posL += 1
        if L_pre < R_pre:
            S += abs(R_pre)
            break
        S += L_pre - R_pre
    ans = S

if R[0] < 0:
    S = abs(R[0])
    R_pre = R[0]
    posL = 0
    posR = 1
    while True:
        L_pre = L[posL]
        posL += 1
        if L_pre < R_pre:
            S += abs(R_pre)
            break
        S += L_pre - R_pre
        R_pre = R[posR]
        posR += 1
        if L_pre < R_pre:
            S += abs(L_pre)
            break
        S += L_pre - R_pre
    ans = max(ans, S)

print ans

Solution (Python):
N = int(input())
L = []
R = []
for i in range(N):
    l, r = map(int, input().split())
    L.append(r)
    R.append(l)
L.sort()
R.sort(reverse=True)
ans = 0
tak = 0
for r, l in zip(R, L):
    if tak < r:
        ans += r - tak
        tak = r
    else:
        break
    if l < tak:
        ans += tak - l
        tak = l
    else:
        break
ans += abs(tak)
ans_ = ans
ans = 0
tak = 0
for r, l in zip(R, L):
    if l < tak:
        ans += tak - l
        tak = l
    else:
        break
    if tak < r:
        ans += r - tak
        tak = r
    else:
        break
ans += abs(tak)
print(max(ans, ans_))

Solution (Python):
from heapq import heappop, heappush
N = int(input())
QL = []
QR = []
for i in range(N):
    L, R = map(int, input().split())
    heappush(QL, (-L, i))
    heappush(QR, (R, i))
QL1 = QL[:]
QR1 = QR[:]

deta = set()
x = 0
ans = 0
for i in range(N):
    if i % 2 == 0:
        for _ in range(N):
            if QL1[0][1] not in deta:
                break
            heappop(QL1)
        L, i = heappop(QL1)
        deta.add(i)
        L = -L
        if x < L:
            ans += L - x
            x = L
    else:
        for _ in range(N):
            if QR1[0][1] not in deta:
                break
            heappop(QR1)
        R, i = heappop(QR1)
        deta.add(i)
        if x > R:
            ans += x - R
            x = R
ans += abs(x)
x = 0
ans1 = 0
deta = set()
for i in range(N):
    if i % 2:
        for _ in range(N):
            if QL[0][1] not in deta:
                break
            heappop(QL)
        L, i = heappop(QL)
        deta.add(i)
        L = -L
        if x < L:
            ans1 += L - x
            x = L
    else:
        for _ in range(N):
            if QR[0][1] not in deta:
                break
            heappop(QR)
        R, i = heappop(QR)
        deta.add(i)
        if x > R:
            ans1 += x - R
            x = R
ans1 += abs(x)

print(max(ans1, ans))