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



Sample input:
3
-5 1
3 7
-4 -2


Sample output:
10

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
Sec=[]
Left1,Right1=[],[]
for i in range(N):
  l,r=map(int,input().split())
  Sec.append((l,r))
  Left1.append((l,i))
  Right1.append((r,i))
Left1.sort()
Right1.sort(reverse=True)
Left2=Left1[:]
Right2=Right1[:]
Used=[False]*N
pos=0
n=0
ans1=0
f_l,f_r=0,0
while Left1 or Right1:
  if n%2==0:
    if not Left1:
      n+=1
      continue
    l,i=Left1[-1]
    if Used[i]:
      Left1.pop()
      continue
    if pos<l:
      ans1+=l-pos
      pos=l
      Used[i]=True
      Left1.pop()
      f_l=0
    else:
      if f_l==1:
        Left1.pop()
        f_l=0
      else:
        f_l=1
    n+=1
  elif n%2==1:
    if not Right1:
      n+=1
      continue
    r,i=Right1[-1]
    if Used[i]:
      Right1.pop()
      continue
    if r<pos:
      ans1+=pos-r
      pos=r
      Used[i]=True
      Right1.pop()
      f_r=0
    else:
      if f_r==1:
        Right1.pop()
        f_r=0
      else:
        f_r=1
    n+=1
  
ans1+=abs(pos)
n=0
ans2=0
Used=[False]*N
f_l,f_r=0,9
pos=0
while Left2 or Right2:
  if n%2==1:
    if not Left2:
      n+=1
      continue
    l,i=Left2[-1]
    if Used[i]:
      Left2.pop()
      continue
    if pos<l:
      ans2+=l-pos
      pos=l
      Used[i]=True
      Left2.pop()
      f_l=0
    else:
      if f_l==1:
        Left2.pop()
        f_l=0
      else:
        f_l=1
    n+=1
  elif n%2==0:
    if not Right2:
      n+=1
      continue
    r,i=Right2[-1]
    if Used[i]:
      Right2.pop()
      continue
    if r<pos:
      ans2+=pos-r
      pos=r
      Used[i]=True
      Right2.pop()
      f_r=0
    else:
      if f_r==1:
        Right2.pop()
        f_r=0
      else:
        f_r=1
    n+=1
    
ans2+=abs(pos)
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a = []
for i in range(n):
  x,y = map(int,input().split())
  a.append([x,y])
l = sorted(a,key=lambda x: -x[0])
r = sorted(a,key=lambda x: x[1])
left = 0
hi = 0
mi = 0
for i in range(n):
  hi += l[i][0]
  left = max(left,(hi-mi)*2)
  mi += r[i][1]
  left = max(left,(hi-mi)*2)
right = 0
hi = 0
mi = 0
for i in range(n):
  mi += r[i][1]
  right = max(right,(hi-mi)*2)
  hi += l[i][0]
  right = max(right,(hi-mi)*2)
print(max(right,left))

Submission status: Accepted

Solution code:
n = int(input())
L,R = [0],[0]
for _ in range(n):
	l,r = (int(i) for i in input().split())
	L.append(l)
	R.append(r)
L,R,ans = sorted(L)[::-1],sorted(R),0
for i in range(n+1):
	if L[i]>R[i]: ans+=L[i]-R[i]
	else: break
print(ans*2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin

in_strings = lambda: stdin.readline()[:-1] # s = in_strings()
in_int = lambda: int(stdin.readline()) # N = in_int()
in_intlist = lambda: list(map(int, stdin.readline().split())) # List = in_intlist()

N = in_int()
L_list = []
R_list = []
for _ in range(N):
    temp = in_intlist()
    L_list.append(temp[0])
    R_list.append(temp[1])

L_list.sort(reverse=True)
R_list.sort()


ans = 0
for i in range(N):
    if (L_list[i] - R_list[i]) > 0:
        ans += 2*(L_list[i] - R_list[i])
    else:
        if (L_list[i] <= 0) and (R_list[i] >= 0):
            pass
        elif L_list[i] > 0:
            if (i>0) and (L_list[i] < R_list[i-1]):
                ans += 2 * R_list[i-1]
            else:
                ans += 2 * L_list[i]
        else:
            if (i>0) and (R_list[i] > L_list[i-1]):
                ans -= 2 * L_list[i-1]
            else:
                ans -= 2 * R_list[i]
        break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

arr = []

for i in range(n):
    a, b = map(int, input().split())
    arr.append([i, a, b])
    
    
left_arr = sorted(arr, key=lambda x: x[2])
right_arr = sorted(arr, key=lambda x: x[1], reverse=True)

ans = 0

f = 0
ok = [0 for i in range(n)]

#if abs(left_arr[0][2]) < abs(right_arr[0][1]):
#    f = 1
    
lp = 0
rp = 0
now = 0
for i in range(n):
    if f == 0:
        while True:
            if ok[left_arr[lp][0]] == 0:
                break
            else:
                lp += 1
        if now >= left_arr[lp][1] and now <= left_arr[lp][2]:
            ans += 0
        elif abs(left_arr[lp][1] - now) < abs(left_arr[lp][2] - now):
            ans += abs(left_arr[lp][1] - now)
            now = left_arr[lp][1]
        else:
            ans += abs(left_arr[lp][2] - now)
            now = left_arr[lp][2]
        ok[left_arr[lp][0]] = 1
        lp += 1
        f = 1
    else:
        while True:
            if ok[right_arr[rp][0]] == 0:
                break
            else:
                rp += 1
        if now >= right_arr[rp][1] and now <= right_arr[rp][2]:
            ans += 0
        elif abs(right_arr[rp][1] - now) < abs(right_arr[rp][2] - now):
            ans += abs(right_arr[rp][1] - now)
            now = right_arr[rp][1]
        else:
            ans += abs(right_arr[rp][2] - now)
            now = right_arr[rp][2]
        ok[right_arr[rp][0]] = 1
        rp += 1
        f = 0
        
ans += abs(now)

temp = ans

ans = 0

f = 1
for i in range(n):
    ok[i] = 0

lp = 0
rp = 0
now = 0
for i in range(n):
    if f == 0:
        while True:
            if ok[left_arr[lp][0]] == 0:
                break
            else:
                lp += 1
        if now >= left_arr[lp][1] and now <= left_arr[lp][2]:
            ans += 0
        elif abs(left_arr[lp][1] - now) < abs(left_arr[lp][2] - now):
            ans += abs(left_arr[lp][1] - now)
            now = left_arr[lp][1]
        else:
            ans += abs(left_arr[lp][2] - now)
            now = left_arr[lp][2]
        ok[left_arr[lp][0]] = 1
        lp += 1
        f = 1
    else:
        while True:
            if ok[right_arr[rp][0]] == 0:
                break
            else:
                rp += 1
        if now >= right_arr[rp][1] and now <= right_arr[rp][2]:
            ans += 0
        elif abs(right_arr[rp][1] - now) < abs(right_arr[rp][2] - now):
            ans += abs(right_arr[rp][1] - now)
            now = right_arr[rp][1]
        else:
            ans += abs(right_arr[rp][2] - now)
            now = right_arr[rp][2]
        ok[right_arr[rp][0]] = 1
        rp += 1
        f = 0
        
        
ans += abs(now)

if temp>ans:
    ans = temp
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
left = []
right = []
for _ in range(n):
    l,r = li()
    left.append(l)
    right.append(r)
    
left.sort(reverse=True)
right.sort(reverse=False)

ans_l = 0
last = 0
for i in range(n):
    if left[i] - last < 0:
        ans_l += abs(last)
        break
    else:
        ans_l += (left[i] - last) 
        last = left[i]
    
    if last - right[i] < 0:
        ans_l += abs(last)
        break
    else:
        ans_l += (last - right[i])
        last = right[i]
    
ans_r = 0
last = 0
for i in range(n):
    if last - right[i] < 0:
        ans_r += abs(last)
        break
    else:
        ans_r += (last - right[i])
        last = right[i]
    
    if left[i] - last < 0:
        ans_r += abs(last)
        break
    else:
        ans_r += (left[i] - last) 
        last = left[i]
    


print(max(ans_l, ans_r))

Submission status: Accepted

Solution code:
n = int(input())
l = [0]
r = [0]
for _ in range(n):
    l1, r1 = map(int, input().split())
    l.append(l1)
    r.append(r1)

l = sorted(l)[::-1]
r.sort()
result = 0
for i in range( n + 1):
    if l[i] > r[i]:
        result += l[i] - r[i]
print(result * 2)

Submission status: Accepted

Solution code:
from itertools import accumulate
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()

L = list(accumulate(L))
R = list(accumulate(R))

ans = 0
for i in range(N):
    ans = max(ans, 2*(L[i] - R[i]))

print(ans)

Submission status: Accepted

Solution code:
import sys


def get_checks(lefts, rights, used):
    def left_check(pos):
        while lefts:
            e, i = lefts.pop()
            if not used[i]:
                break
        else:
            return None

        used[i] = True
        if pos >= e:
            return None
        return e

    def right_check(pos):
        while rights:
            e, i = rights.pop()
            if not used[i]:
                break
        else:
            return None

        used[i] = True
        if pos <= e:
            return None
        return e

    return left_check, right_check


def simulate(left_first=True):
    ans = 0
    pos = 0
    _lefts = lefts.copy()
    _rights = rights.copy()
    used = [False] * n
    left_check, right_check = get_checks(_lefts, _rights, used)
    funcs = [left_check, right_check] if left_first else [right_check, left_check]
    dir = 0

    while True:
        e = funcs[dir](pos)
        if e is None:
            break
        ans += abs(e - pos)
        pos = e
        dir ^= 1
    ans += abs(pos)
    return ans


n = int(input())
lefts, rights = [], []
for i, line in enumerate(sys.stdin.readlines()):
    l, r = map(int, line.split())
    lefts.append((l, i))
    rights.append((r, i))

lefts.sort()
rights.sort(reverse=True)

lf = simulate(True)
rf = simulate(False)

print(max(lf, rf))

Submission status: Accepted

Solution code:
from itertools import accumulate

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()

L = list(accumulate(L))
R = list(accumulate(R))

ans = 0
for k in range(N+1):
    ans = max(ans, 2*(L[k]-R[k]))

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int(input())
L, R = [0], [0]
for i in range(N):
    li, ri = map(int, input().split())
    L.append(li)
    R.append(ri)

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

L = list(accumulate(L))
R = list(accumulate(R))

ans = 0
for k in range(N+1):
    ans = max(ans, 2*(L[k]-R[k]))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]
ls = [0]
rs = [0]
for l,r in src:
    ls.append(l)
    rs.append(r)
ans = 0
for l,r in zip(reversed(sorted(ls)),sorted(rs)):
    if l <= r: break
    ans += 2*(l-r)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int(input())
L, R = [0], [0]
for i in range(N):
    li, ri = map(int, input().split())
    L.append(li)
    R.append(ri)

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

L = list(accumulate(L))
R = list(accumulate(R))

ans = 0
for k in range(N+1):
    ans = max(ans, 2*(L[k] - R[k]))

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
LR=[None]*N
for i in range(N):
    LR[i]=list(map(int,input().split()))

RAN=(len(LR)+1)//2

LR_L=sorted(LR,key=lambda x: x[0],reverse=True)
LR_R=sorted(LR,key=lambda x: x[1])

ANS_l=[0]*(RAN*2+2)
ANS_r=[0]*(RAN*2+2)

for i in range(RAN):
    ANS_l[2*i+1]=ANS_l[2*i]+LR_L[i][0]
    ANS_l[2*i+2]=ANS_l[2*i+1]-LR_R[i][1]

    ANS_r[2*i+1]=ANS_r[2*i]-LR_R[i][1]
    ANS_r[2*i+2]=ANS_r[2*i+1]+LR_L[i][0]


print(max(max(ANS_l)*2,max(ANS_r)*2))

Submission status: Accepted

Solution code:
from itertools import accumulate

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()

L = list(accumulate(L))
R = list(accumulate(R))

ans = 0
for k in range(N+1):
    ans = max(ans, 2*(L[k] - R[k]))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L,R = [None]*N,[None]*N
for i in range(N):
  L[i],R[i] = map(int,input().split())
L.append(0)
R.append(0)
L.sort(reverse=True)
R.sort()

def it():
  for l,r in zip(L,R):
    if r < l:
      yield 2*(l-r)
    else:
      return

print(sum(it()))

Submission status: Accepted

Solution code:
N = int(input())
 
intervals = tuple(tuple(map(int,input().split())) for _ in range(N))
 
L = sorted((l for l,r in intervals))
R = sorted((r for l,r in intervals), reverse=True)
 
def helper(L,R,turn):
  x = 0
  cost = 0
  T = [L,None,R]
  while True:
    y = T[turn+1].pop()
 
    if turn*(y-x) < 0:
      cost += abs(x-y)
      x = y
    else:
      break
    turn *= -1
  cost += abs(x)
  return cost

print(max(helper(L.copy(), R.copy(), t) for t in (-1,1)))

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int(input())
L, R = [0], [0]
for i in range(N):
    li, ri = map(int, input().split())
    L.append(li)
    R.append(ri)

L = list(accumulate(sorted(L, reverse=True)))
R = list(accumulate(sorted(R)))

ans = 0
for k in range(N):
    ans = max(ans, 2*(L[k] - R[k]))

print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
L = []
R = []

for _ in range(N):
  (l, r) = reads()
  L.append(l)
  R.append(-r)

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

psumL = [0] * (N+1)
psumR = [0] * (N+1)

for i in range(N):
  psumL[i+1] = psumL[i] + L[i]
  psumR[i+1] = psumR[i] + R[i]

ans = 0

for i in range(N+1):
  ans = max(ans, psumL[i] + psumR[i])

for i in range(N):
  ans = max(ans, psumL[i] + psumR[i+1])
  ans = max(ans, psumL[i+1] + psumR[i])

print(ans * 2)

Submission status: Accepted

Solution code:
n = int(input())

l = []
r = []
for i in range(n):
    lt, rt = map(int,input().split())
    l.append(lt)
    r.append(rt)

l.append(0)
r.append(0)

l.sort()
r.sort()
l.reverse()

ans = 0
i = 0
while r[i]<l[i]:
    ans += 2*(l[i] - r[i])
    i+=1

print(ans)

Submission status: Accepted

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

# 原点を追加
L.append(0)
R.append(0)

# 左端点は降順に、右端点は昇順にソート
L.sort(reverse=True)
R.sort()

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

print(Ans)

Submission status: Accepted

Solution code:
N = int(input())
L = [0]*N
R = [0]*N

for i in range(N):
	L[i],R[i] = map(int,input().split(" "))
L.sort(reverse=True)
R.sort()
ans = 0
acc = 0
for i in range(N):
	ans = max(ans,acc+2*L[i])
	acc += (2*(L[i]-R[i]))
	ans = max(ans,acc)

acc = 0
for i in range(N):
	ans = max(ans,acc+2*(-R[i]))
	acc += (2*(L[i]-R[i]))
	ans = max(ans,acc)

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import deque
N = int(input())
L = [[0,0]]
for i in range(N):
    l,r = map(int,input().split())
    L.append([l,r])
Q = sorted(L)
R = sorted(L,key=itemgetter(1))
ans = 0
suma=0
for i in range(N//2+1):
    suma +=2*(Q[-i-1][0]-R[i][1])
    if suma>ans:
        ans = suma
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

l_sort = sorted(lr, key=itemgetter(0), reverse=True)
r_sort = sorted(lr, key=itemgetter(1))

ans = 0
sigma = 0

for i in range(n // 2 + 1):
	sigma += 2 * (l_sort[i][0] - r_sort[i][1])
	if sigma > ans:
		ans = sigma

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N = int(input())
S = []
for i in range(N):
    l, r = map(int, input().split())
    S.append((l, r))

if all(l <= 0 <= r for l, r in S):
    print(0)
    exit(0)

P = sorted(r for l, r in S)
Q = sorted(l for l, r in S)
L = R = 0
ans = 0
for i in range(N):
    if not i < N-1-i:
        break
    L += P[i]
    R += Q[N-1-i]
    ans = max(ans, abs(R - L)*2)
    if i+1 < N-1-i:
        ans = max(ans, abs(R - L - P[i+1])*2)
    if i < N-1-i-1:
        ans = max(ans, abs(R + Q[N-1-i-1] - L)*2)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N = int(input())
S = []
for i in range(N):
    l, r = map(int, input().split())
    S.append((l, r))

if all(l <= 0 <= r for l, r in S):
    print(0)
    exit(0)

P = sorted(r for l, r in S)
Q = sorted(l for l, r in S)
L = R = 0
ans = 0
for i in range(N):
    if not i < N-1-i:
        break
    L += P[i]
    R += Q[N-1-i]
    ans = max(ans, abs(R - L)*2)
    if i+1 < N-1-i:
        ans = max(ans, abs(R - L - P[i+1])*2)
    if i < N-1-i-1:
        ans = max(ans, abs(R + Q[N-1-i-1] - L)*2)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N = int(input())
S = []
for i in range(N):
    l, r = map(int, input().split())
    S.append((l, r))
S.sort()

if all(l <= 0 <= r for l, r in S):
    print(0)
    exit(0)

que = []
P = []
Q = [l for l, r in S]
Q.reverse()
ans = 0
a = b = 0
p = 0
for i in range(N+1):
    if i < N:
        l, r = S[i]
    while que and que[0] <= l:
        P.append(heappop(que))
    cnt = min(len(P), len(Q))
    while p < cnt:
        a += P[p]
        b += Q[p]
        p += 1
    ans = max(ans, abs(a-b)*2)
    if len(P) < len(Q):
        b2 = b + Q[cnt]
        ans = max(ans, abs(a-b2)*2)
    elif len(P) > len(Q):
        a2 = a + P[cnt]
        ans = max(ans, abs(a2-b)*2)
    heappush(que, r)
    if cnt == len(Q) > 0:
        a -= P[cnt-1]
        b -= Q[cnt-1]
    if i < N:
        Q.pop()
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
LRs = []
for i in range(N):
    L, R = map(int, input().split())
    LRs += [(L, R, i)]

Ls = sorted(LRs)
Rs = sorted(LRs, key=lambda x: x[1])


# 1手目がマイナス方向の場合
done = [False] * N
iL = N - 1
iR = 0
ans1 = 0
xNow = 0
while True:
    # マイナス方向に移動
    while iR < N and done[Rs[iR][2]]: iR += 1
    if iR == N: break

    xNext = Rs[iR][1]
    if xNow < xNext: break

    ans1 += xNow - xNext
    xNow = xNext
    done[Rs[iR][2]] = True

    # プラス方向に移動
    while iL >= 0 and done[Ls[iL][2]]: iL -= 1
    if iL < 0: break

    xNext = Ls[iL][0]
    if xNext < xNow: break

    ans1 += xNext - xNow
    xNow = xNext
    done[Ls[iL][2]] = True

ans1 += abs(xNow)


# 1手目がプラス方向の場合
done = [False] * N
iL = N - 1
iR = 0
ans2 = 0
xNow = 0
while True:
    # プラス方向に移動
    while iL >= 0 and done[Ls[iL][2]]: iL -= 1
    if iL < 0: break

    xNext = Ls[iL][0]
    if xNext < xNow: break

    ans2 += xNext - xNow
    xNow = xNext
    done[Ls[iL][2]] = True

    # マイナス方向に移動
    while iR < N and done[Rs[iR][2]]: iR += 1
    if iR == N: break

    xNext = Rs[iR][1]
    if xNow < xNext: break

    ans2 += xNow - xNext
    xNow = xNext
    done[Rs[iR][2]] = True

ans2 += abs(xNow)

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
N = int(input())
sect = []
sect_l = []
sect_r = []

for i in range(N):
	l,r = map(int,input().split())
	sect_l.append((l,r,i))
	sect_r.append((r,l,i))
	sect.append((l,r))

sect_l.sort()
sect_r.sort()
sect_r.reverse()

ans_l,ans_r = 0,0
if sect_r[N-1][0] < 0:
	used = [False for i in range(N)]
	L = [x for x in sect_l]
	R = [x for x in sect_r]
	next = 'L'
	cur = 0
	cnt = 0
	while cnt < N:
		if next == 'R':
			while True:
				l,r,i = L.pop()
				if not used[i]:
					used[i] = True
					break
			if not (l <= cur and cur <= r):
				ans_l += abs(cur - l)
				cur = l
			next = 'L'
			cnt += 1
		else:
			while True:
				r,l,i = R.pop()
				if not used[i]:
					used[i] = True
					break
			if not (l <= cur and cur <= r):
				ans_l += abs(cur - r)
				cur = r
			next = 'R'
			cnt += 1
	ans_l += abs(cur)

if sect_l[N-1][0] > 0:
	used = [False for i in range(N)]
	L = [x for x in sect_l]
	R = [x for x in sect_r]
	next = 'R'
	cur = 0
	cnt = 0
	while cnt < N:
		if next == 'R':
			while True:
				l,r,i = L.pop()
				if not used[i]:
					used[i] = True
					break
			if not (l <= cur and cur <= r):
				ans_r += abs(cur - l)
				cur = l
			next = 'L'
			cnt += 1
		else:
			while True:
				r,l,i = R.pop()
				if not used[i]:
					used[i] = True
					break
			if not (l <= cur and cur <= r):
				ans_r += abs(cur - r)
				cur = r
			next = 'R'
			cnt += 1
	ans_r += abs(cur)
print(max(ans_l,ans_r))

Submission status: Accepted

Solution code:
# C
from heapq import heappush, heappop

N = int(input())
L_arr = [0]*N
R_arr = [0]*N

for i in range(N):
    L, R = map(int, input().split())
    L_arr[i] = L
    R_arr[i] = R

# argsort
R_args = [0]*N
h = []
for i in range(N):
    heappush(h, (R_arr[i], i))
for i in range(N):
    a, b = heappop(h)
    R_args[i] = b
L_args = [0]*N
h = []
for i in range(N):
    heappush(h, (-L_arr[i], i))
for i in range(N):
    a, b = heappop(h)
    L_args[i] = b



# Greedy Left
used_idx = [0]*N
res = 0
pos = 0
i_r = 0
i_l = 0

for i in range(N):
    while used_idx[L_args[i_l]] == 1:
        i_l += 1
    while used_idx[R_args[i_r]] == 1:
        i_r += 1
        
    # run
    if i % 2 == 0:
        used_idx[L_args[i_l]] = 1
        if L_arr[L_args[i_l]] > pos:
            res += L_arr[L_args[i_l]] - pos
            pos = L_arr[L_args[i_l]]
            #print(pos)
        elif R_arr[L_args[i_l]] < pos:
            res += pos - R_arr[L_args[i_l]]
            pos = R_arr[L_args[i_l]]
            #print(pos)
    else:
        used_idx[R_args[i_r]] = 1
        if R_arr[R_args[i_r]] < pos:
            res += pos - R_arr[R_args[i_r]]
            pos = R_arr[R_args[i_r]]
            #print(pos)
        elif L_arr[R_args[i_r]] > pos:
            res += L_arr[R_args[i_r]] - pos
            pos = L_arr[R_args[i_r]]
            #print(pos)
res_1 = res + abs(pos)

# Greedy Left
used_idx = [0]*N
res = 0
pos = 0
i_r = 0
i_l = 0

for i in range(N):
    while used_idx[L_args[i_l]] == 1:
        i_l += 1
    while used_idx[R_args[i_r]] == 1:
        i_r += 1
        
    # run
    if i % 2 != 0:
        used_idx[L_args[i_l]] = 1
        if L_arr[L_args[i_l]] > pos:
            res += L_arr[L_args[i_l]] - pos
            pos = L_arr[L_args[i_l]]
        elif R_arr[L_args[i_l]] < pos:
            res += pos - R_arr[L_args[i_l]]
            pos = R_arr[L_args[i_l]]
    else:
        used_idx[R_args[i_r]] = 1
        if R_arr[R_args[i_r]] < pos:
            res += pos - R_arr[R_args[i_r]]
            pos = R_arr[R_args[i_r]]
        elif L_arr[R_args[i_r]] > pos:
            res += L_arr[R_args[i_r]] - pos
            pos = L_arr[R_args[i_r]]
res_2 = res + abs(pos)

print(max(res_1, res_2))

Submission status: Accepted

Solution code:
N = int(input())

intervals = list(tuple(map(int,input().split())) for _ in range(N))

L = sorted(((l,i) for i,(l,r) in enumerate(intervals)))
R = sorted(((r,i) for i,(l,r) in enumerate(intervals)), reverse=True)

def helper(L,R,turn):
  used = [False]*(N+1)
  used[N] = True

  x = 0
  cost = 0
  while True:
    A = [L,None,R][turn+1]

    i = N
    while used[i]:
      y,i = A.pop()

    if turn*(y-x) < 0:
      cost += abs(x-y)
      x = y
    else:
      break
    turn *= -1
  cost += abs(x)
  return cost

print(max(helper(L.copy(), R.copy(), t) for t in [-1,1]))

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n = f.read_int()

    lside = []
    rside = []
    for ind in xrange(n):
        l, r = f.read_int_list()
        heapq.heappush(lside, (r, -l, ind))
        heapq.heappush(rside, (-l, r, ind))
    used = collections.defaultdict(bool)
    lside_dup = lside[:]
    rside_dup = rside[:]

    ans1 = 0
    cur = 0
    for i in xrange(n):
        l, r = 0, 0
        if i%2 == 0:
            while True:
                a, b, ind = heapq.heappop(lside)
                l, r = -b, a
                if not used[ind]:
                    used[ind] = True
                    break
        else:
            while True:
                a, b, ind = heapq.heappop(rside)
                l, r = -a, b
                if not used[ind]:
                    used[ind] = True
                    break

        if l <= cur <= r:
            pass
        elif cur < l:
            ans1 += l-cur
            cur = l
        else:
            ans1 += cur-r
            cur = r
    ans1 += abs(cur)

    lside = lside_dup
    rside = rside_dup
    used = collections.defaultdict(bool)
    ans2 = 0
    cur = 0
    for i in xrange(n):
        l, r = 0, 0
        if i%2 == 1:
            while True:
                a, b, ind = heapq.heappop(lside)
                l, r = -b, a
                if not used[ind]:
                    used[ind] = True
                    break
        else:
            while True:
                a, b, ind = heapq.heappop(rside)
                l, r = -a, b
                if not used[ind]:
                    used[ind] = True
                    break

        if l <= cur <= r:
            pass
        elif cur < l:
            ans2 += l-cur
            cur = l
        else:
            ans2 += cur-r
            cur = r
    ans2 += abs(cur)

    return max(ans1, ans2)


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 pf(s): return print(s, flush=True)

def main():
    n = I()
    a = [LI() + [_] for _ in range(n)]
    r = 0
    la = sorted(a,key=lambda x: [-x[0],-x[0]])
    ra = sorted(a,key=lambda x: [x[1],x[0]])
    u = set()
    li = 0
    ri = 0
    tr = 0
    c = 0
    for i in range(len(a)//2 + len(a) % 2):
        while li < n and la[li][2] in u:
            li += 1
        if c < la[li][0]:
            tr += la[li][0] - c
            c = la[li][0]
        u.add(la[li][2])

        while ri < n and ra[ri][2] in u:
            ri += 1
        if ri == n:
            break
        if c > ra[ri][1]:
            tr += c - ra[ri][1]
            c = ra[ri][1]
        u.add(ra[ri][2])

    r = tr + abs(c)
    u = set()
    li = 0
    ri = 0
    tr = 0
    c = 0
    for i in range(len(a)//2 + len(a) % 2):
        while ri < n and ra[ri][2] in u:
            ri += 1
        if c > ra[ri][1]:
            tr += c - ra[ri][1]
            c = ra[ri][1]
        u.add(ra[ri][2])

        while li < n and la[li][2] in u:
            li += 1
        if li == n:
            break
        if c < la[li][0]:
            tr += la[li][0] - c
            c = la[li][0]
        u.add(la[li][2])
    if tr + abs(c) > r:
        r = tr + abs(c)

    return r


print(main())