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: Wrong Answer

Solution code:
def main():
    
    #0 input
    N = int(input())
    LR = []
    for i in range(N):
        LR.append(list(map(int, input().split())))
    
    LR_sorted = sorted(LR, reverse=True)
    takahashi = 0
    moved = 0
    
    
    while 1:
        #1 choose maximum L
        next_interval  = LR_sorted[0]
        
        # finish if Takahashi is in the next interval
        if next_interval[0] <= takahashi and takahashi <= next_interval[1]:
            break
        
        moved += next_interval[0] - takahashi
        takahashi = next_interval[0]
        
        # delete the current interval
        del LR_sorted[0]
        
        # finish if no items in the list
        if len(LR_sorted) == 0:
            break
        
        
        #2 choose minimum R
        next_interval = min(LR_sorted, key=lambda x:x[1])
        
        # finish if Takahashi is in the next interval
        if next_interval[0] <= takahashi and takahashi <= next_interval[1]:
            break
        
        moved += takahashi - next_interval[1]
        takahashi = next_interval[1]
        
        # delete the current interval
        LR_sorted.remove(next_interval)
        
        # finish if no items in the list
        if len(LR_sorted) == 0:
            break
        
        
    moved += abs(0-takahashi)
    print(moved)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def ii():
    return int(input())


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


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


# def remove(a, l, r, k):
#     N = len(a)
#     i, j = 0, N-1
#     p = N // 2
#
#     while i < j:
#         if a[p][k] == v:
#             del a[p]
#             return a
#         elif a[p][k] > v:
#             j = p
#         elif a[p][k] < v:
#             i = p+1
#
#         p = (i + j) // 2

def next_p(now, l, r):
    if r < now:
        return r, now - r
    elif now < l:
        return l, l - now
    else:
        return now, 0


def solve(N, sort, args, direct='R'):
    used = [0 for _ in range(N)]

    rp = 0
    lp = N-1

    # print(sort, args)

    ans = 0
    now = 0
    for _ in range(N):

        if direct == 'R':
            while used[args[lp][0]] == 1:
                lp -= 1
            ix = args[lp][0]
            used[ix] = 1

            now, d = next_p(now, sort[lp][0], sort[lp][1])
        else:
            while used[args[rp][1]] == 1:
                rp += 1
            ix = args[rp][1]
            used[ix] = 1

            now, d = next_p(now, sort[rp][0], sort[rp][1])
        ans += d

        if direct == 'L':
            direct = 'R'
        else:
            direct = 'L'

    ans += abs(now)
    return ans


def main():
    N = ii()
    Q = []

    for _ in range(N):
        l, r = lii()
        Q.append([l, r])

    Q = np.array(Q)

    sort = np.sort(Q, axis=0)
    args = np.argsort(Q, axis=0)

    ans1 = solve(N, sort, args, 'L')
    ans2 = solve(N, sort, args, 'R')
    print(max(ans1, ans2))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = input()
    L = [0 for i in range(N)]
    R = [0 for i in range(N)]
    intervals = []
    K = 0
    for i in range(N):
        L[i], R[i] = map(int, raw_input().split())
    current = 0
    for i in range(N):
        maxL = max(L)
        minR = min(R)
        if abs(current-maxL) > abs(current-minR):
            index = L.index(maxL)
            nowL = L.pop(index)
            nowR = R.pop(index)
            if current > nowL:
                pass
            else:
                K = K + (nowL - current)
                current = nowL
        else:
            index = R.index(minR)
            nowL = L.pop(index)
            nowR = R.pop(index)
            if current < minR:
                pass
            else:
                K = K + (current - nowR)
                current = nowR
    K = K + abs(current)
    print(K)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for l, r in LR:
    if l > 0:
        L.append([l, r])
    elif r < 0:
        R.append([l, r])

L.sort(reverse=True, key=lambda x: x[0])
R.sort(key=lambda x: x[1])

L2, R2 = [], []
if L:
    for i in range((len(L) // 2)+1):
        if len(L2) == len(L):
            break
        L2.append(L[i])
        if len(L2) == len(L):
            break
        L2.append(L[len(L)-i-1])

if R:
    for i in range((len(R) // 2)+1):
        if len(R2) == len(R):
            break
        R2.append(R[i])
        if len(R2) == len(R):
            break
        R2.append(R[len(R)-i-1])

m = min(len(L2), len(R2))
Z = [[0, 0]]

for i in range(m):
    Z.append(L2[i])
    Z.append(R2[i])

if len(L2) > len(R2):
    for i in range(m, len(L2)):
        Z.append(L2[i])

if len(R2) > len(L2):
    for i in range(m, len(R2)):
        Z.append(R2[i])

ans = 0
tail = 0
now = (Z[0][0] if Z[0][0] > 0 else Z[0][1])
#print(Z)
for z in Z[1:]:

    if z[0] <= now <= z[1]:
        continue

    if now < z[0]:
        ans += abs(z[0]-now)
        now = z[0]

    elif z[1] < now:
        ans += abs(z[1] - now)
        now = z[1]

print(ans + abs(now))

Submission status: Wrong Answer

Solution code:
n = int(input())
L,R = [],[]
for num in range(n):
	l,r = (int(i) for i in input().split())
	L.append(l)
	R.append(r)
L,R,a,b = sorted(L),sorted(R),-1,0
if R and L and R[0]<=0 and L[-1]>=0:
	if abs(R[0])<L[-1]: flag,now,ans,a = True,L[-1],L[-1],-2
	else: flag,now,ans,b = False,R[0],abs(R[0]),1
elif R and L and R[0]<=0 and L[-1]<0: flag,now,ans,b = False,R[0],abs(R[0]),1
elif R and L and R[0]>0 and L[-1]>=0: flag,now,ans,a = True,L[-1],L[-1],-2
else: ans,now = 0,0
while ans!=0 and b-a!=len(L)+1 and ((flag and R[b]<now) or (not flag and now<L[a])):
	if flag: flag,now,ans,b = False,R[b],ans+abs(now-R[b]),b+1
	else: flag,now,ans,a = True,L[a],ans+abs(now-L[a]),a-1
print(ans+abs(now))

Submission status: Wrong Answer

Solution code:
N = int(input())

plus_l = []
minus_l = []

for _ in range(N):
    l, r = list(map(int, input().split(" ")))
    if l * r > 0:
        if l < 0:
            minus_l.append(-max(l, r))
        else:
            plus_l.append(min(r, l))

plus_l = sorted(plus_l)[::-1]
minus_l = sorted(minus_l)[::-1]

# print(plus_l, minus_l)

if abs(len(plus_l) - len(minus_l)) <= 1:

    print(2*sum(plus_l) + 2*sum(minus_l))

elif len(plus_l) > len(minus_l) + 1:
    del_num = len(plus_l) - len(minus_l) - 1
    # print(del_num)
    plus_l = plus_l[:-del_num]
    print(2*sum(plus_l) + 2*sum(minus_l))

elif len(minus_l) > len(plus_l) + 1:
    del_num = len(minus_l) - len(plus_l) - 1
    # print(del_num)
    minus_l = minus_l[:-del_num]
    print(2*sum(plus_l) + 2*sum(minus_l))

Submission status: Wrong Answer

Solution code:
n = int(input())
L,R = [],[]
for num in range(n):
	l,r = (int(i) for i in input().split())
	if l<=0<=r: continue
	L.append(l)
	R.append(r)
L,R,a,b = sorted(L),sorted(R),-1,0
if R and L and R[0]<=0 and L[-1]>=0:
	if abs(R[0])<L[-1]: flag,now,ans,a = True,L[-1],L[-1],-2
	else: flag,now,ans,b = False,R[0],abs(R[0]),1
elif R and L and R[0]<=0 and L[-1]<0: flag,now,ans,b = False,R[0],abs(R[0]),1
elif R and L and R[0]>0 and L[-1]>=0: flag,now,ans,a = True,L[-1],L[-1],-2
else: ans,now = 0,0
while ans!=0 and b-a!=len(L)+1 and ((flag and R[b]<now) or (not flag and now<L[a])):
	if flag: flag,now,ans,b = False,R[b],ans+abs(now-R[b]),b+1
	else: flag,now,ans,a = True,L[a],ans+abs(now-L[a]),a-1
print(ans+abs(now))

Submission status: Wrong Answer

Solution code:
import heapq as hq

N = int(input())

ispush = []
L,R = [],[]
LR = []
for i in range(N):
    l,r = map(int,input().split())
    hq.heappush(L,(l*(-1),i)) #取り出す時は-1を掛け直すことに注意
    hq.heappush(R,(r,i))
    LR.append([l,r])
    ispush.append(False)

side = True #Trueで右(Lを追う側に行く)
sl = min(L)[0]*(-1) #実質max
sr = min(R)[0]
if sl*sr>0: #同符号
    if sl>0: side = True
    else: side = False
else: #異符号
    if abs(sr)>abs(sl): side = False

ans = 0
now = 0
for i in range(N):
    #選ぶ
    mov = 0
    if side: #L追う
        while(True):
            if len(L)==0:break
            mov = hq.heappop(L)
            if not ispush[mov[1]]: break
    else:
        while(True):
            if len(R)==0:break
            mov = hq.heappop(R)
            if not ispush[mov[1]]: break
    ispush[mov[1]] = True
    #移動する
    if now < LR[mov[1]][0] or LR[mov[1]][1] < now:
        if side:
            ans += abs((mov[0]*(-1))-now)
            now = mov[0]*(-1)
            side = False
        else:
            ans += abs(mov[0]-now)
            now = mov[0]
            side = True
    #print(now)
            
print(ans+abs(now))

Submission status: Wrong Answer

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

for l, r in LR:
    if l > 0:
        L.append([l, r])
    elif r < 0:
        R.append([l, r])

L.sort(reverse=True, key=lambda x: x[0])
R.sort(key=lambda x: x[1])

L2, R2 = [], []
if L:
    for i in range((len(L) // 2)+1):
        if len(L2) == len(L):
            break
        L2.append(L[i])
        if len(L2) == len(L):
            break
        L2.append(L[len(L)-i-1])

if R:
    for i in range((len(R) // 2)+1):
        if len(R2) == len(R):
            break
        R2.append(R[i])
        if len(R2) == len(R):
            break
        R2.append(R[len(R)-i-1])

m = min(len(L2), len(R2))
Z = [[0, 0]]

for i in range(m):
    Z.append(L2[i])
    Z.append(R2[i])

if len(L2) > len(R2):
    for i in range(m, len(L2)):
        Z.append(L2[i])

if len(R2) > len(L2):
    for i in range(m, len(R2)):
        Z.append(R2[i])

ans = 0
tail = 0
now = (Z[0][0] if Z[0][0] > 0 else Z[0][1])
#print(Z)
for z in Z[1:]:

    if now < z[0]:
        ans += abs(z[0]-now)
        now = z[0]

    elif z[1] < now:
        ans += abs(z[1] - now)
        now = z[1]

print(ans + abs(now))

Submission status: Wrong Answer

Solution code:
N = int(input())
P = []; Q = []; R = []
for i in range(N):
    l, r = map(int, input().split())
    if r < 0:
        P.append((l, r))
    elif l > 0:
        Q.append((l, r))
    else:
        R.append((l, r))
P.sort(key=lambda x: (x[1], x[0]), reverse=1)
Q.sort()

ans = 0
M = min(len(P), len(Q))
for i in range(M):
    lp, rp = P.pop()
    lq, rq = Q.pop()
    ans += (-rp + lq) * 2
if P:
    rest = N - 2*M
    cnt = min((rest + 1) // 2, len(P))
    R.extend(P[:-cnt])
    P = P[-cnt:]
    R.sort()
    if cnt:
        lp, rp = P.pop()
        ans += (-rp)*2
        for i in range(cnt-1):
            lp, rp = P.pop()
            lr, rr = R.pop()
            if not rp < lr:
                break
            ans += (-rp)*2 - (-lr)*2
if Q:
    rest = N - 2*M
    cnt = min((rest + 1) // 2, len(Q))
    R.extend(Q[:-cnt])
    Q = Q[-cnt:]
    R.sort(key=(lambda x: (x[1], x[0])), reverse=1)

    if cnt:
        lq, rq = Q.pop()
        ans += lq*2
        for i in range(cnt-1):
            lq, rq = Q.pop()
            lr, rr = R.pop()
            if not rr < lq:
                break
            ans += lq*2 - rr*2
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
import heapq


def move(p, l, r):
    if p < l:
        p = l
    elif p > r:
        p = r
    return p


def main():
    N = int(input())

    hl = []
    hr = []
    md = (0, 0, 0, 0)
    for i in range(N):
        l, r = map(int, input().split())
        heapq.heappush(hl, (-l, r, i))
        heapq.heappush(hr, (r, l, i))

        d = abs(move(0, l, r))
        # sys.stderr.write("{} -> {}\n".format(str((l, r)), d))
        if d > md[0]:
            md = (d, i, l, r)
        # sys.stderr.write(str(md) + "\n")

    used = [False] * N
    ans = md[0]
    used[md[1]] = True
    p = move(0, md[2], md[3])
    if p > 0:
        mode = 1                # right
    else:
        mode = 0                # left / center?

    while hr and hl:
        # sys.stderr.write("pos: {}, mode: {}\n".format(p, mode))
        if mode == 0:
            if len(hl) == 0:
                mode = 1
                continue
            l, r, i = heapq.heappop(hl)
            l = -l
        else:
            if len(hr) == 0:
                mode = 0
                continue
            r, l, i = heapq.heappop(hr)
        # sys.stderr.write("r: {}\n".format(str((-l, r, i))))
        # sys.stderr.write(" used: {}\n".format(used[i]))
        if not used[i]:
            used[i] = True
            np = move(p, l, r)
            ans += abs(p-np)
            if np-p > 0:
                mode = 1
            else:
                mode = 0
            p = np
    ans += abs(p)
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
# def slv(N, LR):
#     L = sorted(filter(lambda x: x[0] < 0 and x[1] < 0, LR), key=lambda x: x[1])
#     R = sorted(
#         filter(lambda x: x[0] > 0 and x[1] > 0, LR),
#         key=lambda x: x[0],
#         reverse=True)

#     B = filter(lambda x: x[0] <= 0 and x[1] >= 0, LR)

#     p = 0
#     ans = 0
#     for _ in range(N):
#         error_print(p)
#         if len(L) == 0 and len(R) == 0:
#             break
#         if len(L) > len(R):
#             t = L.pop(0)
#             ans += abs(t[1] - p)
#             p = t[1]
#         elif len(L) < len(R):
#             t = R.pop(0)
#             ans += abs(t[0] - p)
#             p = t[0]
#         elif abs(L[0][1] - p) > abs(R[0][0] - p):
#             t = L.pop(0)
#             ans += abs(t[1] - p)
#             p = t[1]
#         else:
#             t = R.pop(0)
#             ans += abs(t[0] - p)
#             p = t[0]

#     error_print(p)
#     ans += p

#     return ans


@mt
def slv(N, LR):
    L = sorted(filter(lambda x: x[0] < 0 and x[1] < 0, LR), key=lambda x: x[1])
    R = sorted(
        filter(lambda x: x[0] > 0 and x[1] > 0, LR),
        key=lambda x: x[0],
        reverse=True)

    B = filter(lambda x: x[0] <= 0 and x[1] >= 0, LR)

    p = 0
    ans = 0
    for _ in range(N):
        error_print(p)
        if len(L) == 0 and len(R) == 0:
            break
        if len(L) > len(R):
            if min(abs(L[0][1] - p), abs(L[0][0] - p)) > \
               min(abs(L[-1][1] - p), abs(L[-1][0] - p)):
                t = L.pop(0)
                if abs(t[1] - p) < abs(t[0] - p):
                    ans += abs(t[1] - p)
                    p = t[1]
                else:
                    ans += abs(t[0] - p)
                    p = t[0]
            else:
                t = L.pop()
                if abs(t[1] - p) < abs(t[0] - p):
                    ans += abs(t[1] - p)
                    p = t[1]
                else:
                    ans += abs(t[0] - p)
                    p = t[0]
        elif len(L) < len(R):
            if min(abs(R[0][0] - p), abs(R[0][1] - p)) > \
            min(abs(R[-1][0] - p), abs(R[-1][1] - p)):
                t = R.pop(0)
                if abs(t[1] - p) < abs(t[0] - p):
                    ans += abs(t[1] - p)
                    p = t[1]
                else:
                    ans += abs(t[0] - p)
                    p = t[0]
            else:
                t = R.pop()
                if abs(t[1] - p) < abs(t[0] - p):
                    ans += abs(t[1] - p)
                    p = t[1]
                else:
                    ans += abs(t[0] - p)
                    p = t[0]
        elif abs(L[0][1] - p) > abs(R[0][0] - p):
            if min(abs(L[0][1] - p), abs(L[0][0] - p)) > \
               min(abs(L[-1][1] - p), abs(L[-1][0] - p)):
                t = L.pop(0)
                if abs(t[1] - p) < abs(t[0] - p):
                    ans += abs(t[1] - p)
                    p = t[1]
                else:
                    ans += abs(t[0] - p)
                    p = t[0]
            else:
                t = L.pop()
                if abs(t[1] - p) < abs(t[0] - p):
                    ans += abs(t[1] - p)
                    p = t[1]
                else:
                    ans += abs(t[0] - p)
                    p = t[0]
        else:
            if min(abs(R[0][0] - p), abs(R[0][1] - p)) > \
            min(abs(R[-1][0] - p), abs(R[-1][1] - p)):
                t = R.pop(0)
                if abs(t[1] - p) < abs(t[0] - p):
                    ans += abs(t[1] - p)
                    p = t[1]
                else:
                    ans += abs(t[0] - p)
                    p = t[0]
            else:
                t = R.pop()
                if abs(t[1] - p) < abs(t[0] - p):
                    ans += abs(t[1] - p)
                    p = t[1]
                else:
                    ans += abs(t[0] - p)
                    p = t[0]

    error_print(p)
    ans += abs(p)

    return ans


def main():
    N = read_int()
    LR = [read_int_n() for _ in range(N)]
    print(slv(N, LR))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq as hq

N = int(input())

ispush = []
L,R = [],[]
LR = []
side = True #Trueで右(Lを追う側に行く)
for i in range(N):
    l,r = map(int,input().split())
    hq.heappush(L,(l*(-1),i)) #取り出す時は-1を掛け直すことに注意
    hq.heappush(R,(r,i))
    LR.append([l,r])
    ispush.append(False)

sl = abs(min(L)[0])
sr = abs(min(R)[0])
if sr>sl: side = False

ans = 0
now = 0
for i in range(N):
    #選ぶ
    mov = 0
    if side: #L追う
        while(True):
            if len(L)==0:break
            mov = hq.heappop(L)
            if not ispush[mov[1]]: break
    else:
        while(True):
            if len(R)==0:break
            mov = hq.heappop(R)
            if not ispush[mov[1]]: break
    ispush[mov[1]] = True
    #移動する
    if now < LR[mov[1]][0] or LR[mov[1]][1] < now:
        if side:
            ans += abs((mov[0]*(-1))-now)
            now = mov[0]*(-1)
            side = False
        else:
            ans += abs(mov[0]-now)
            now = mov[0]
            side = True
    #print(now)
            
print(ans+abs(now))

Submission status: Wrong Answer

Solution code:
import sys                                                                                                              
n = int(input())                                                                                                        
areas = []                                                                                                              
class Area:                                                                                                             
    def __init__(self, s):                                                                                              
        l, r = s.split()                                                                                                
        self.l = int(l)                                                                                                 
        self.r = int(r)                                                                                                 
for i in range(n):                                                                                                      
    areas.append(Area(input()))                                                                                         
                                                                                                                        
l1 = sorted(areas, key=lambda a: a.r)                                                                                   
l2 = sorted(areas, key=lambda a: a.l, reverse=True)                                                                     
moves = []                                                                                                              
                                                                                                                        
if abs(l1[0].r) < l2[0].l:                                                                                              
    a = l2.pop(0)                                                                                                       
    del l1[l1.index(a)]                                                                                                 
    moves.append(a.l)                                                                                                   
                                                                                                                        
while l1:                                                                                                               
    a = l1.pop(0)                                                                                                       
    del l2[l2.index(a)]                                                                                                 
    moves.append(a.r)                                                                                                   
    if not l1:                                                                                                          
        break                                                                                                           
    a = l2.pop(0)                                                                                                       
    del l1[l1.index(a)]                                                                                                 
    moves.append(a.l)                                                                                                   
moves.append(0)                                                                                                         
                                                                                                                        
p = 0                                                                                                                   
d = 0                                                                                                                   
for m in moves:                                                                                                         
    d += abs(p - m)                                                                                                     
    p = m                                                                                                               
print(d)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
import heapq


def move(p, l, r):
    if p < l:
        p = l
    elif p > r:
        p = r
    return p


def main():
    N = int(input())

    hl = []
    hr = []
    md = (0, 0, 0, 0)
    for i in range(N):
        l, r = map(int, input().split())
        heapq.heappush(hl, (-l, r, i))
        heapq.heappush(hr, (r, l, i))

        d = abs(move(0, l, r))
        # sys.stderr.write("{} -> {}\n".format(str((l, r)), d))
        if d > md[0]:
            md = (d, i, l, r)
        # sys.stderr.write(str(md) + "\n")

    used = [False] * N
    ans = md[0]
    used[md[1]] = True
    p = move(0, md[2], md[3])
    if p > 0:
        mode = 1                # right
    else:
        mode = 0                # left / center?

    while hr and hl:
        # sys.stderr.write("pos: {}, mode: {}\n".format(p, mode))
        if mode == 0:
            if len(hl) == 0:
                mode = 1
                continue
            l, r, i = heapq.heappop(hl)
            # sys.stderr.write("r: {}\n".format(str((-l, r, i))))
            # sys.stderr.write(" used: {}\n".format(used[i]))
            if not used[i]:
                used[i] = True
                l = -l
                np = move(p, l, r)
                ans += abs(p-np)
                p = np
                mode = 1
        else:
            if len(hr) == 0:
                mode = 0
                continue
            r, l, i = heapq.heappop(hr)
            # sys.stderr.write("l: {}\n".format(str((l, r, i))))
            # sys.stderr.write(" used: {}\n".format(used[i]))
            if not used[i]:
                used[i] = True
                np = move(p, l, r)
                ans += abs(p-np)
                p = np
                mode = 0
    ans += abs(p)
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def ng(a):
    return [(-y, -x) for x, y in a]
def go(p, ab=abs):
    p.sort(reverse=True)
    m = [y for x, y in p[(len(p)+1)/2:]]
    m.sort()
    p = p[:(len(p)+1)/2]
    ans = 0
    pr = 0
    for x, y in p:
        if x <= 0 <= y:
            x = 0
        elif y < 0:
            x = y
        ans += ab(x - pr)
        pr = x
        if m:
            t = m.pop()
            if pr > t:
                ans += ab(pr - t)
                pr = t
    if m and m[-1] < pr:
        ans += ab(pr - m[-1])
        pr = m[-1]
    ans += abs(pr)
    return ans
def main():
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n))
    a = []
    for i in xrange(n):
        a.append(dat[i*2:i*2+2])
    print max(go(a), go(ng(a)))
main()

Submission status: Wrong Answer

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

for l, r in LR:
    if l > 0:
        L.append([l, r])
    elif r < 0:
        R.append([l, r])

L.sort(reverse=True, key=lambda x: x[0])
R.sort(reverse=True, key=lambda x: x[1])

L2, R2 = [], []
if L:
    for i in range((len(L) // 2)+1):
        if len(L2) == len(L):
            break
        L2.append(L[i])
        if len(L2) == len(L):
            break
        L2.append(L[len(L)-i-1])

if R:
    for i in range((len(R) // 2)+1):
        if len(R2) == len(R):
            break
        R2.append(R[i])
        if len(R2) == len(R):
            break
        R2.append(R[len(R)-i-1])

m = min(len(L2), len(R2))
Z = [[0, 0]]

for i in range(m):
    Z.append(L2[i])
    Z.append(R2[i])

if len(L2) > len(R2):
    for i in range(m, len(L2)):
        Z.append(L2[i])

if len(R2) > len(L2):
    for i in range(m, len(R2)):
        Z.append(R2[i])

ans = 0
tail = 0
now = (Z[0][0] if Z[0][0] > 0 else Z[0][1])

for z in Z[1:]:

    if now < 0 < z[0]:
        ans += abs(z[0]-now)
        now = z[0]

    elif 0 <= now < z[0]:
        ans += abs(z[0]-now)
        now = z[0]

    elif 0 <= z[1] < now:
        ans += abs(z[1] - now)
        now = z[1]

    elif z[1] < 0 < now:
        ans += abs(z[1] - now)
        now = z[1]

    elif z[1] < now <= 0:
        ans += abs(z[1] - now)
        now = z[1]

    elif now < z[0] < 0:
        ans += abs(z[0] - now)
        now = z[0]

print(ans + abs(now))

Submission status: Wrong Answer

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
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
    
    # left
    if L_arr[L_args[i_l]] > pos:
        compare_left = L_arr[L_args[i_l]] - pos
    elif R_arr[L_args[i_l]] < pos:
        compare_left = pos - R_arr[L_args[i_l]]
    else:
        compare_left = 0
    
    # right
    if R_arr[R_args[i_r]] < pos:
        compare_right = pos - R_arr[R_args[i_r]]
    elif L_arr[R_args[i_r]] > pos:
        compare_right = L_arr[R_args[i_r]] - pos
    else:
        compare_right = 0
        
    # run
    res += max(compare_left, compare_right)
    if compare_left >= compare_right:
        used_idx[L_args[i_l]] = 1
        if L_arr[L_args[i_l]] > pos:
            pos = L_arr[L_args[i_l]]
        elif R_arr[L_args[i_l]] < pos:
            pos = R_arr[L_args[i_l]]
    else:
        used_idx[R_args[i_r]] = 1
        if R_arr[R_args[i_r]] < pos:
            pos = R_arr[R_args[i_r]]
        elif L_arr[R_args[i_r]] > pos:
            pos = L_arr[R_args[i_r]]
        
print(res+abs(pos))