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:
I,i,H=input,int,range
n,L,R,A,C=i(I()),[],[],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)

Submission status: Wrong Answer

Solution code:
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])
#print(l, r)
res = 0
vis = [0] * N
x = 0
for i in range(N):
  #print(l, r, vis, x, res)
  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]):
      res += 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]):
      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):
  #print(l, r, vis, x, rres)
  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))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
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#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
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は64bit整数
    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():
    #C - Interval Game
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    base=10**5
    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
    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)
    print(tot)




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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 = min(calc(left, right), calc(left_inv, right_inv))
print(ans)

Submission status: Wrong Answer

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

N = int(input())
left = []
right = []
for i in range(N):
    L, R = map(int, input().split())
    left.append((R, i))
    right.append((L, i))
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)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
llr = []
rlr = []
zlr = []
for i in range(n):
    l,r = map(int, input().split())
    if l<=0<=r:
        zlr.append((l,r))
    elif r<=0:
        llr.append((l,r))
    else:
        rlr.append((l,r))
nl = len(llr)
nr = len(rlr)    
if nl>nr:
    llr = [(-t[0], -t[1]) for t in llr]
    rlr = [(-t[0], -t[1]) for t in rlr]
    zlr = [(-t[0], -t[1]) for t in zlr]
    nl, nr = nr, nl
from heapq import heappop as hpp, heappush as hp, heapify
def sub1():
    hr = []
    hl = []
    i = 0
    from itertools import chain
    for item in chain(zlr, llr, rlr):
        hp(hr, (item[1], i))
        hp(hl, (-item[0], i))
        i += 1
    ans = 0
    done = set()
    c = 0
    while True:
        i = None
        while hl:
            l, i = hpp(hl)
            l *= -1
            if i not in done:
                break
            else:
                i = None
        if i is None or l<=c:
            break
        done.add(i)
    #     print(i, l, done)
        ans += abs(c-l)
        c = l

        i = None
        while hr:
            r, i = hpp(hr)
            if i not in done:
                break
            else:
                i = None
        if i is None or c<=r:
            break
        done.add(i)
    #     print(i,r,done)
        ans += abs(c-r)
        c = r
    ans += abs(c)
    return ans
def sub2():
    hr = []
    hl = []
    i = 0
    from itertools import chain
    for item in chain(zlr, llr, rlr):
        hp(hr, (item[1], i))
        hp(hl, (-item[0], i))
        i += 1
    ans = 0
    done = set()
    c = 0
    while True:
        i = None
        while hr:
            r, i = hpp(hr)
            if i not in done:
                break
            else:
                i = None
        if i is None or c<=r:
            break
        done.add(i)
    #     print(i,r,done)
        ans += abs(c-r)
        c = r
        
        i = None
        while hl:
            l, i = hpp(hl)
            l *= -1
            if i not in done:
                break
            else:
                i = None
        if i is None or l<=c:
            break
        done.add(i)
    #     print(i, l, done)
        ans += abs(c-l)
        c = l

    ans += abs(c)
    return ans

ans = sub1()
ans = max(ans, sub2())
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
llr = []
rlr = []
zlr = []
for i in range(n):
    l,r = map(int, input().split())
    if l<=0<=r:
        zlr.append((l,r))
    elif r<=0:
        llr.append((l,r))
    else:
        rlr.append((l,r))
nl = len(llr)
nr = len(rlr)    
if nl>nr:
    llr = [(-t[0], -t[1]) for t in llr]
    rlr = [(-t[0], -t[1]) for t in rlr]
    zlr = [(-t[0], -t[1]) for t in zlr]
    nl, nr = nr, nl
from heapq import heappop as hpp, heappush as hp, heapify

if abs(nr-nl)<=1:
    ans = sum(-t[1]*2 for t in llr) + sum(t[0]*2 for t in rlr)
else:
    hr = []
    hl = []
    i = 0
    from itertools import chain
    for item in chain(zlr, llr, rlr):
        hp(hr, (item[1], i))
        hp(hl, (-item[0], i))
        i += 1
    ans = 0
    done = set()
    c = 0
    while True:
        i = None
        while hl:
            l, i = hpp(hl)
            l *= -1
            if i not in done:
                break
            else:
                i = None
        if i is None or l<=c:
            break
        done.add(i)
#         print(i, l, done)
        ans += abs(c-l)
        c = l
        
        i = None
        while hr:
            r, i = hpp(hr)
            if i not in done:
                break
            else:
                i = None
        if i is None or c<=r:
            break
        done.add(i)
#         print(i,r,done)
        ans += abs(c-r)
        c = r
    ans += abs(c)        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
llr = []
rlr = []
zlr = []
for i in range(n):
    l,r = map(int, input().split())
    if l<=0<=r:
        zlr.append((l,r))
    elif r<=0:
        llr.append((l,r))
    else:
        rlr.append((l,r))
nl = len(llr)
nr = len(rlr)    
if nl>nr:
    llr = [(-t[0], -t[1]) for t in llr]
    rlr = [(-t[0], -t[1]) for t in rlr]
    zlr = [(-t[0], -t[1]) for t in zlr]
    nl, nr = nr, nl
from heapq import heappop as hpp, heappush as hp, heapify

if abs(nr-nl)<=1:
    ans = sum(-t[1]*2 for t in llr) + sum(t[0]*2 for t in rlr)
else:
    hr = []
    hl = []
    i = 0
    from itertools import chain
    for item in chain(zlr, llr, rlr):
        hp(hr, (item[1], i))
        hp(hl, (-item[0], i))
        i += 1
    ans = 0
    done = set()
    c = 0
    while True:
        i = None
        while hl:
            l, i = hpp(hl)
            l *= -1
            if i not in done:
                break
            else:
                i = None
        if i is None:
            break
        done.add(i)
#         print(i, l, done)
        ans += abs(c-l)
        c = l
        
        i = None
        while hr:
            r, i = hpp(hr)
            if i not in done:
                break
            else:
                i = None
        if i is None:
            break
        done.add(i)
#         print(i,r,done)
        ans += abs(c-r)
        c = r
    ans += abs(c)        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n = int(readline())
lr = list(map(int,read().split()))
done = [0] * n

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

ans = 0
now = 0
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)
print(ans)

Submission status: Wrong Answer

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

N = int(input())
dp = [[-10**18]*3 for _ in range(N+1)]
dp[0][1] = 0

for i in range(N):
    L, R = map(int, input().split())
    dp[i+1][0] = max(dp[i][0], dp[i][1]-2*R)
    dp[i+1][1] = max(dp[i][0]+2*L, dp[i][1], dp[i][2]-2*R)
    dp[i+1][2] = max(dp[i][1]+2*L, dp[i][2])

print(max(dp[N]))

Submission status: Wrong Answer

Solution code:
import heapq

N=int(input())
rque=[]
lque=[]
for i in range(N):
    l,r=map(int,input().split())
    rque.append((-l,i))
    lque.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

print(ans+abs(pos))

Submission status: Wrong Answer

Solution code:
"""
C
"""
import sys

N=int(input())

LR=[]
RL=[]

for i in range(N):
    L,R=map(int,input().split())
    LR.append([L,R,i])
    RL.append([R,L,i])
    
LR.sort(reverse=True)
RL.sort()

if LR[-1][0]<=0 and RL[-1][0]<=0:
    print(0)
    sys.exit()
    
flag=[0]*N
ans=0
x=0
for i in range(N):
    if x<LR[i][0]:
        ans+=LR[i][0]-x
        x=LR[i][0]
        if x>RL[i][0]:
            ans+=x-RL[i][0]
            x=RL[i][0]
        else:
            break
            
    elif x>RL[i][0]:
        ans+=x-RL[i][0]
        x=RL[i][0]
        if x<LR[i][0]:
            ans+=LR[i][0]-x
            x=LR[i][0]
        else:
            break
            
    else:
        break
        
ans+=abs(x)

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(x):
        if x[1] < 0:
            return x[1]
        if x[0] > 0:
            return x[0]
        return 0
    n = I()
    p = LIR(n)
    p.sort(key = lambda x : f(x))
    x = 0
    ans = 0
    l = 0
    r = n-1
    while l <= r:
        a,b = p[l]
        l += 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
        if l > r:
            break
        a,b = p[r]
        r -= 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
    m = ans+abs(x)
    x = 0
    ans = 0
    l = 0
    r = n-1
    while l <= r:
        a,b = p[r]
        r -= 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
        a,b = p[l]
        l += 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
        if l > r:
            break
    ans += abs(x)
    print(max(m,ans))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    p.sort(key = lambda x : max(x[0],min(0,x[1])))
    x = 0
    ans = 0
    l = 0
    r = n-1
    while l <= r:
        a,b = p[l]
        l += 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
        if l > r:
            break
        a,b = p[r]
        r -= 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
    m = ans+abs(x)
    x = 0
    ans = 0
    l = 0
    r = n-1
    while l <= r:
        a,b = p[r]
        r -= 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
        a,b = p[l]
        l += 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
        if l > r:
            break
    ans += abs(x)
    print(max(m,ans))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    p.sort(key = lambda x : max(x[0],min(0,x[1])))
    if p[0][1] < p[-1][0]:
        p = p[::-1]
    x = 0
    ans = 0
    l = 0
    r = n-1
    while l <= r:
        a,b = p[l]
        l += 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
        if l > r:
            break
        a,b = p[r]
        r -= 1
        if x < a:
            ans += a-x
            x = a
        elif b < x:
            ans += x-b
            x = b
    ans += abs(x)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())

LR = []
for _ in range(N):
	LR.append(tuple(map(int, input().split())))

ans = 0

LR = sorted(LR, key=itemgetter(1))
if N % 2 == 0:
	LR1 = LR[0:N//2]
	LR2 = sorted(LR[N//2:], key=itemgetter(0))
	ans = 0
	loc = 0
	for i in range(N//2):
		if loc < LR1[i][0] or LR1[i][1] < loc:
			if abs(loc - LR1[i][0]) < abs(loc - LR1[i][1]):
				loc_next = LR1[i][0]
			else:
				loc_next = LR1[i][1]
			ans += abs(loc_next - loc)
			loc = loc_next
		if loc < LR2[-i-1][0] or LR2[-i-1][1] < loc:
			if abs(loc - LR2[-i - 1][0]) < abs(loc - LR2[-i - 1][1]):
				loc_next = LR2[-i - 1][0]
			else:
				loc_next = LR2[-i - 1][1]
			ans += abs(loc_next - loc)
			loc = loc_next
	ans += abs(loc)

	ans2 = 0
	loc = 0
	for i in range(N//2):
		if loc < LR2[-i-1][0] or LR2[-i-1][1] < loc:
			if abs(loc - LR2[-i-1][0]) < abs(loc - LR2[-i-1][1]):
				loc_next = LR2[-i-1][0]
			else:
				loc_next = LR2[-i-1][1]
			ans2 += abs(loc_next - loc)
			loc = loc_next
		if loc < LR1[i][0] or LR1[i][1] < loc:
			if abs(loc - LR1[i][0]) < abs(loc - LR1[i][1]):
				loc_next = LR1[i][0]
			else:
				loc_next = LR1[i][1]
			ans2 += abs(loc_next - loc)
			loc = loc_next
	ans2 += abs(loc)
	print(max(ans, ans2))
else:
	LR1 = LR[0:N//2]
	LR1.append((0, 0))
	LR2 = sorted(LR[N//2:], key=itemgetter(0))
	ans = 0
	loc = 0
	for i in range(N//2 + 1):
		if loc < LR2[-i-1][0] or LR2[-i-1][1] < loc:
			if abs(loc - LR2[-i-1][0]) < abs(loc - LR2[-i-1][1]):
				loc_next = LR2[-i-1][0]
			else:
				loc_next = LR2[-i-1][1]
			ans += abs(loc_next - loc)
			loc = loc_next
		if loc < LR1[i][0] or LR1[i][1] < loc:
			if abs(loc - LR1[i][0]) < abs(loc - LR1[i][1]):
				loc_next = LR1[i][0]
			else:
				loc_next = LR1[i][1]
			ans += abs(loc_next - loc)
			loc = loc_next
	LR1 = LR[0:N//2 + 1]
	LR2 = sorted(LR[N//2 + 1:], key=itemgetter(0))
	LR2 = [(0, 0)] + LR2
	ans2 = 0
	loc = 0
	for i in range(N//2 + 1):
		if loc < LR1[i][0] or LR1[i][1] < loc:
			if abs(loc - LR1[i][0]) < abs(loc - LR1[i][1]):
				loc_next = LR1[i][0]
			else:
				loc_next = LR1[i][1]
			ans2 += abs(loc_next - loc)
			loc = loc_next
		if loc < LR2[-i-1][0] or LR2[-i-1][1] < loc:
			if abs(loc - LR2[-i - 1][0]) < abs(loc - LR2[-i - 1][1]):
				loc_next = LR2[-i - 1][0]
			else:
				loc_next = LR2[-i - 1][1]
			ans2 += abs(loc_next - loc)
			loc = loc_next
	print(max(ans, ans2))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())

LR = []
for _ in range(N):
	LR.append(tuple(map(int, input().split())))

ans = 0

LR = sorted(LR, key=itemgetter(1))
if N % 2 == 0:
	LR1 = LR[0:N//2]
	LR2 = sorted(LR[N//2:], key=itemgetter(0))
	ans = 0
	loc = 0
	for i in range(N//2):
		if loc < LR1[i][0] or LR1[i][1] < loc:
			if abs(loc - LR1[i][0]) < abs(loc - LR1[i][1]):
				loc_next = LR1[i][0]
			else:
				loc_next = LR1[i][1]
			ans += abs(loc_next - loc)
			loc = loc_next
		if loc < LR2[-i-1][0] or LR2[-i-1][1] < loc:
			if abs(loc - LR2[-i - 1][0]) < abs(loc - LR2[-i - 1][1]):
				loc_next = LR2[-i - 1][0]
			else:
				loc_next = LR2[-i - 1][1]
			ans += abs(loc_next - loc)
			loc = loc_next
	ans += abs(loc)

	ans2 = 0
	loc = 0
	for i in range(N//2):
		if loc < LR2[-i-1][0] or LR2[-i-1][1] < loc:
			if abs(loc - LR2[-i-1][0]) < abs(loc - LR2[-i-1][1]):
				loc_next = LR2[-i-1][0]
			else:
				loc_next = LR2[-i-1][1]
			ans2 += abs(loc_next - loc)
			loc = loc_next
			print(ans2, loc)
		if loc < LR1[i][0] or LR1[i][1] < loc:
			if abs(loc - LR1[i][0]) < abs(loc - LR1[i][1]):
				loc_next = LR1[i][0]
			else:
				loc_next = LR1[i][1]
			ans2 += abs(loc_next - loc)
			loc = loc_next
	ans2 += abs(loc)
	print(max(ans, ans2))
else:
	LR1 = LR[0:N//2]
	LR1.append((0, 0))
	LR2 = sorted(LR[N//2:], key=itemgetter(0))
	ans = 0
	loc = 0
	for i in range(N//2 + 1):
		if loc < LR2[-i-1][0] or LR2[-i-1][1] < loc:
			if abs(loc - LR2[-i-1][0]) < abs(loc - LR2[-i-1][1]):
				loc_next = LR2[-i-1][0]
			else:
				loc_next = LR2[-i-1][1]
			ans += abs(loc_next - loc)
			loc = loc_next
		if loc < LR1[i][0] or LR1[i][1] < loc:
			if abs(loc - LR1[i][0]) < abs(loc - LR1[i][1]):
				loc_next = LR1[i][0]
			else:
				loc_next = LR1[i][1]
			ans += abs(loc_next - loc)
			loc = loc_next
	LR1 = LR[0:N//2 + 1]
	LR2 = sorted(LR[N//2 + 1:], key=itemgetter(0))
	LR2 = [(0, 0)] + LR2
	ans2 = 0
	loc = 0
	for i in range(N//2 + 1):
		if loc < LR1[i][0] or LR1[i][1] < loc:
			if abs(loc - LR1[i][0]) < abs(loc - LR1[i][1]):
				loc_next = LR1[i][0]
			else:
				loc_next = LR1[i][1]
			ans2 += abs(loc_next - loc)
			loc = loc_next
		if loc < LR2[-i-1][0] or LR2[-i-1][1] < loc:
			if abs(loc - LR2[-i - 1][0]) < abs(loc - LR2[-i - 1][1]):
				loc_next = LR2[-i - 1][0]
			else:
				loc_next = LR2[-i - 1][1]
			ans2 += abs(loc_next - loc)
			loc = loc_next
	print(max(ans, ans2))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    def comb(a,b):
        return fact[a]*inv_fact[b]*inv_fact[a-b]%mod
    mod = 998244353
    n,a,b,k = LI()
    fact = [1]*(n+1)
    for i in range(1,n+1):
        fact[i] = fact[i-1]*i%mod
    inv_fact = [None]*(n+1)
    inv_fact[n] = pow(fact[n],mod-2,mod)
    for i in range(n)[::-1]:
        inv_fact[i] = inv_fact[i+1]*(i+1)%mod

    ans = 0
    for x in range(n+1):
        if (k-a*x)%b == 0 and k >= a*x and k-a*x <= n*b:
            y = (k-a*x)//b
            ans += comb(n,x)*comb(n,y)%mod
        ans %= mod
    print(ans)

#C
def C():
    n = I()
    d = LIR(n)
    x = [None for i in range(n)]
    for i in range(n):
        if d[i][0]*d[i][1] <= 0:
            x[i] = 0
        else:
            if d[i][1] < 0:
                x[i] = d[i][1]
            else:
                x[i] = d[i][0]
    x.sort(key = lambda x:x)
    l = 0
    r = n-1
    ans = abs(x[l])
    k = 1
    while r-l > 0:
        ans += x[r]-x[l]
        if k:
            k = 0
            l += 1
        else:
            k = 1
            r -= 1
    ans += abs(x[r])
    l = 0
    r = n-1
    ans2 = abs(x[r-1])
    k = 0
    while r-l > 0:
        ans2 += x[r]-x[l]
        if k:
            k = 0
            l += 1
        else:
            k = 1
            r -= 1
    ans2 += abs(x[r])
    print(max(ans,ans2))
#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())
Sec=[]
Left,Right=[],[]
for i in range(N):
  l,r=map(int,input().split())
  Sec.append((l,r))
  Left.append((l,i))
  Right.append((r,i))
Left.sort()
Right.sort(reverse=True)

Used=[False]*N
pos=0
n=0
ans=0
f_l,f_r=0,0
while Left or Right:
  if n%2==0:
    if not Left:
      n+=1
      continue
    l,i=Left[-1]
    if Used[i]:
      Left.pop()
      continue
    if pos<l:
      ans+=l-pos
      pos=l
      Used[i]=True
      Left.pop()
      f_l=0
    else:
      if f_l==1:
        Left.pop()
        f_l=0
      else:
        f_l=1
    n+=1
  elif n%2==1:
    if not Right:
      n+=1
      continue
    r,i=Right[-1]
    if Used[i]:
      Right.pop()
      continue
    if r<pos:
      ans+=pos-r
      pos=r
      Used[i]=True
      Right.pop()
      f_r=0
    else:
      if f_r==1:
        Right.pop()
        f_r=0
      else:
        f_r=1
    n+=1
  
ans+=abs(pos)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())
Sec=[]
Left,Right=[],[]
for i in range(N):
  l,r=map(int,input().split())
  Sec.append((l,r))
  Left.append((l,i))
  Right.append((r,i))
Left.sort()
Right.sort(reverse=True)
Used=[False]*N
pos=0
n=0
ans=0
while Left or Right:
  if n%2==0:
    if not Left:
      n+=1
      continue
    l,i=Left.pop()
    if Used[i]:
      continue
    if pos<l:
      ans+=l-pos
      pos=l
    elif Sec[i][1]<pos:
      ans+=pos-Sec[i][1]
      pos=Sec[i][1]
    Used[i]=True
    n+=1
  elif n%2==1:
    if not Right:
      n+=1
      continue
    r,i=Right.pop()
    if Used[i]:
      continue
    if r<pos:
      ans+=pos-r
      pos=r
    elif Sec[i][0]>pos:
      ans+=Sec[i][0]-pos
      pos=Sec[i][0]
    Used[i]=True
    n+=1
  
ans+=abs(pos)
print(ans)