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:
# coding: utf-8

import sys
import math
import fractions
import heapq
import collections
import re
import array
import bisect

from collections import Counter, defaultdict


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]
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: {}\n".format(p))
        if mode == 0:
            if len(hr) == 0:
                mode = 1
                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
                r = -r
                np = move(p, l, r)
                ans += abs(p-np)
                p = np
                mode = 1
        else:
            if len(hl) == 0:
                mode = 0
                continue
            l, r, i = heapq.heappop(hl)
            # 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):
    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:
        ans += x - pr
        pr = x
        if m:
            t = m.pop()
            if pr > t:
                ans += pr - t
                pr = t
    if m and m[-1] < 0:
        ans += 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())
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:
	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:
from sys import stdin
from itertools import repeat
def ng(a):
    return [(-y, -x) for x, y in a]
def go(p):
    p.sort(reverse=True)
    m = [y for x, y in p[(len(p)+1)/2:]]
    m.sort(reverse=True)
    p = p[:(len(p)+1)/2]
    ans = 0
    pr = 0
    for x, y in p:
        ans += x - pr
        pr = x
        if m:
            t = m.pop()
            if pr > t:
                ans += pr - t
                pr = t
    if m and m[-1] < 0:
        ans += 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:
# C
import numpy as np

N = int(input())
L_arr = np.zeros((N), dtype="int32")
R_arr = np.zeros((N), dtype="int32")

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

R_args = np.argsort(R_arr)
L_args = np.argsort(-L_arr)


# Greedy
used_idx = np.zeros((N), dtype="int32")
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))

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N =int(input())
ku = np.zeros((N, 2),dtype=int)

for i in range(N):
    l=list(map(int, input().split()))
    ku[i][0] = l[0]
    ku[i][1] = l[1]
    

K = 0
now=0
for i in range(N):
    a = np.zeros(len(ku))
    flag=np.zeros(len(ku))
    for j in range(len(ku)):
        if now > ku[j][0] and now < ku[j][1]:
            a[j] = 0
            flag[j]=0
        elif now < ku[j][0]:
            a[j] = abs(now - ku[j][0])
            flag[j]=1
        else:
            a[j] = abs(now - ku[j][1])
            flag[j]=2
    idx = a.argmax()
    K += a[idx]

    if flag[idx] == 1:
        now = ku[idx][0]
    elif flag[idx] == 2:
        now = ku[idx][1]
    ku= np.delete(ku, 0, 0)

K+=abs(now)
print(int(K))

Submission status: Wrong Answer

Solution code:
import numpy as np
N =int(input())
ku = np.zeros((N, 2),dtype=int)

for i in range(N):
    l=list(map(int, input().split()))
    ku[i][0] = l[0]
    ku[i][1] = l[1]
    

K = 0
now=0
for i in range(N):
    a = np.zeros(len(ku))
    flag=[]
    for j in range(len(ku)):
        if now > ku[j][0] and now < ku[j][1]:
            a[j] = 0
            flag.append(0)
        elif now < ku[j][0]:
            a[j] = abs(now - ku[j][0])
            flag.append(1)
        else:
            a[j] = abs(now - ku[j][1])
            flag.append(2)
    idx = a.argmax()
    K += a[idx]

    if flag[idx] == 1:
        now = ku[idx][0]
    elif flag[idx] == 2:
        now = ku[idx][1]
    ku=new = np.delete(ku, 0, 0)

K+=abs(now)
print(int(K))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import copy
input = sys.stdin.buffer.readline

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

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

ans1 += abs(prev)

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

ans2 += abs(prev)

print(max(ans1, ans2))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
  x,y = map(int,input().split())
  a.append([x,y])
ans = 0
ima = 0
for j in range(n):
  ban = -1
  to = 0
  for i in range(len(a)):
    if a[i][0] <= ima and a[i][1]>= ima:
      continue
    toa = min(abs(ima-a[i][0]),abs(ima-a[i][1]))
    if to < toa:
      ban = i
      to = toa
  if ban ==-1:
    print(ans+abs(ima))
    break
  ans += to
  if abs(ima-a[ban][0])>abs(ima-a[ban][1]):
    ima = a[ban][1]
  else:
    ima = a[ban][0]
  a.pop(ban)
else:
  print(ans+abs(ima))

Submission status: Time Limit Exceeded

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

if len(LR)%2==1:
    LR=LR+[[0,0]]

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=0
for k in range(RAN):
    SUB=0
    for i in range(k+1):
        SUB+=LR_L[i][0]-LR_R[i][1]
        ANS=max(SUB,ANS)

print(ANS*2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
LR = []
L = []
R = []
for i in range(N):
    l, r = list(map(int, input().split()))
    LR.append((l, r))
    L.append((i, l))
    R.append((i, r))
L.sort(key=lambda x:x[1])
R.sort(key=lambda x:x[1])
used = [False for _ in range(N)]
#print(L)
#print(R)

def left_id():
    i = N-1
    while used[L[i][0]]==True:
        i -= 1
    return i
def right_id():
    i = 0
    while used[R[i][0]]==True:
        i += 1
    return i


pos = 0
ans = 0
d = 0

idl,l = L[left_id()]
idr,r = R[right_id()]
if abs(pos-r)>abs(pos-l):
    used[idr] = True
    d = 1
    if pos<LR[idr][0] or LR[idr][1]<pos:
        ans += abs(pos - r)
        pos = r
else:
    used[idl] = True
    d = -1
    if pos<LR[idl][0] or LR[idl][1]<pos:
        ans += abs(pos - l)
        pos = l

for i in range(N-1):
    if d==1:
        id, next_pos = L[left_id()]
    else:
        id, next_pos = R[right_id()]
    #print(used)
    #print(i, pos, ans, next_pos)

    used[id] = True
    d *= -1
    if pos<LR[id][0] or LR[id][1]<pos:
        ans += abs(pos - next_pos)
        pos = next_pos

print(ans+abs(pos))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N =int(input())
ku = np.zeros((N, 2),dtype=int)

for i in range(N):
    l=list(map(int, input().split()))
    ku[i][0] = l[0]
    ku[i][1] = l[1]
    

K = 0
now=0
for i in range(N):
    a = np.zeros(len(ku))
    flag=np.zeros(len(ku))
    for j in range(len(ku)):
        if now > ku[j][0] and now < ku[j][1]:
            a[j] = 0
            flag[j]=0
        elif now < ku[j][0]:
            a[j] = abs(now - ku[j][0])
            flag[j]=1
        else:
            a[j] = abs(now - ku[j][1])
            flag[j]=2
    idx = a.argmax()
    K += a[idx]

    if flag[idx] == 1:
        now = ku[idx][0]
    elif flag[idx] == 2:
        now = ku[idx][1]
    ku= np.delete(ku, idx, 0)

K+=abs(now)
print(int(K))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = [[int(i) for i in input().split()] for i in range(N)]
cor = 0
sum = 0

Larr = sorted(arr, key=lambda x:(x[0]))
Rarr = sorted(arr, key=lambda x:(x[1]), reverse=True)
for i in range(N):
    if Larr[N-1-i][0]-cor < cor-Rarr[N-1-i][1]:
        if Rarr[N-1-i][0] > cor or cor > Rarr[N-1-i][1]:
             sum += cor-Rarr[N-1-i][1]
             cor = Rarr[N-1-i][1]

        Larr.remove(Rarr[N-1-i])
        Rarr.pop()
    else:
        if Larr[N-1-i][0] > cor or cor > Larr[N-1-i][1]:
             sum += Larr[N-1-i][0]-cor
             cor = Larr[N-1-i][0]

        Rarr.remove(Larr[N-1-i])
        Larr.pop()

sum += abs(cor)
print("{}".format(sum))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = [[int(i) for i in input().split()] for i in range(N)]
cor = 0
sum = 0

Larr = sorted(arr, key=lambda x:(x[0]), reverse=True)
Rarr = sorted(arr, key=lambda x:(x[1]))
for i in range(N):
    if Larr[0][0]-cor < cor-Rarr[0][1]:
        if Rarr[0][0] > cor or cor > Rarr[0][1]:
             sum += cor-Rarr[0][1]
             cor = Rarr[0][1]

        Larr.remove(Rarr[0])
        Rarr.pop(0)
    else:
        if Larr[0][0] > cor or cor > Larr[0][1]:
             sum += Larr[0][0]-cor
             cor = Larr[0][0]

        Rarr.remove(Larr[0])
        Larr.pop(0)

sum += abs(cor)
print("{}".format(sum))

Submission status: Time Limit Exceeded

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 R[L.index(maxL)] is minR:
            nowL = L.pop()
            nowR = R.pop()
            if current < nowL:
                K = K + (nowL - current)
                current = nowL
            elif current > nowR:
                K = K + (current - nowR)
                current = nowR
            else:
                pass
        elif 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: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

ans = 0
used = []
now = 0
i = 0
j = 0

if abs(l_sort[0][0]) >= abs(r_sort[0][1]):
	while len(used) != n:
		while l_sort[i][2] in used:
			i += 1
		if not (l_sort[i][0] <= now and now <= l_sort[i][1]):
			ans += abs(now - l_sort[i][0])
			now = l_sort[i][0]
		used.append(l_sort[i][2])
		i += 1
		if len(used) == n:
			break
		while r_sort[j][2] in used:
			j += 1
		if not (r_sort[j][0] <= now and now <= r_sort[j][1]):
			ans += abs(now - r_sort[j][1])
			now = r_sort[j][1]
		used.append(r_sort[j][2])
		j += 1

	print(ans + abs(now))

else:
	while len(used) != n:
		while r_sort[j][2] in used:
			j += 1
		if not (r_sort[j][0] <= now and now <= r_sort[j][1]):
			ans += abs(now - r_sort[j][1])
			now = r_sort[j][1]
		used.append(r_sort[j][2])
		j += 1
		if len(used) == n:
			break
		while l_sort[i][2] in used:
			i += 1
		if not (l_sort[i][0] <= now and now <= l_sort[i][1]):
			ans += abs(now - l_sort[i][0])
			now = l_sort[i][0]
		used.append(l_sort[i][2])
		i += 1
		#print(now)

	print(ans + abs(now))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
li1 = np.array([])
li2 = np.array([])
for i in range(N):
    x1, x2 = map(int, input().split())
    li1 = np.append(li1, x1)    
    li2 = np.append(li2, x2)

li1 = np.sort(li1)[::-1]
li2 = np.sort(li2)

result = 0
now = 0
i = 0
j = 0
while(True):
    pos = li1[i]
    if (pos <= now):
        dis = 0
    else:
        dis = pos - now
        now = pos
    result += dis
    
    if ((j != 0) & (dis == 0)):
        break
    j += 1
    if (j == N):
        break
    
    pos = li2[i]
    if (now <= pos):
        dis = 0
    else:
        dis = now - pos
        now = pos
    result += dis
    if (dis == 0):
        break
    i += 1
    j += 1
    if (j == N):
        break

result += np.abs(now)
print(int(result))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
K = 0
r = []
for i in range(N):
    rr = list(map(int, input().split()))
    r.append(rr)
r = np.array(r)

t_pos = 0

for i in range(N):
    d_each = abs(r -t_pos)
    choiced = np.argmax([min(dd) for dd in d_each]) #idx
    if min(r[choiced]) <= t_pos <= max(r[choiced]):
        pass
    else:
        K += min(d_each[choiced])

        if d_each[choiced][0] == d_each[choiced][1]:
            dx = min(abs(d_each[choiced][0]), abs(d_each[choiced][1]))
        else:
            dx = r[choiced][np.argmin(d_each[choiced])]
        t_pos = dx

    r = np.delete(r, choiced, 0)


K += abs(t_pos)
print(K)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

ans = 0
used = set()
now = 0
i = 0
j = 0

if abs(l_sort[0][0]) >= abs(r_sort[0][1]):
	while used != set(range(n)):
		while l_sort[i][2] in used:
			i += 1
		if not (l_sort[i][0] <= now and now <= l_sort[i][1]):
			ans += abs(now - l_sort[i][0])
			now = l_sort[i][0]
		used.add(l_sort[i][2])
		i += 1
		#print(now)
		if used == set(range(n)):
			break
		while r_sort[j][2] in used:
			j += 1
		if not (r_sort[j][0] <= now and now <= r_sort[j][1]):
			ans += abs(now - r_sort[j][1])
			now = r_sort[j][1]
		used.add(r_sort[j][2])
		j += 1
		#print(now)

	print(ans + abs(now))

else:
	while used != set(range(n)):
		while r_sort[j][2] in used:
			j += 1
		if not (r_sort[j][0] <= now and now <= r_sort[j][1]):
			ans += abs(now - r_sort[j][1])
			now = r_sort[j][1]
		used.add(r_sort[j][2])
		j += 1
		#print(now)
		if used == set(range(n)):
			break
		while l_sort[i][2] in used:
			i += 1
		if not (l_sort[i][0] <= now and now <= l_sort[i][1]):
			ans += abs(now - l_sort[i][0])
			now = l_sort[i][0]
		used.add(l_sort[i][2])
		i += 1
		#print(now)

	print(ans + abs(now))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

ans = 0
used = set()
now = 0
i = 0
j = 0

while used != set(range(n)):
	while l_sort[i][2] in used:
		i += 1
	if not (l_sort[i][0] <= now and now <= l_sort[i][1]):
		ans += abs(now - l_sort[i][0])
		now = l_sort[i][0]
	used.add(l_sort[i][2])
	i += 1
	#print(now)
	if used == set(range(n)):
		break
	while r_sort[j][2] in used:
		j += 1
	if not (r_sort[j][0] <= now and now <= r_sort[j][1]):
		ans += abs(now - r_sort[j][1])
		now = r_sort[j][1]
	used.add(r_sort[j][2])
	j += 1
	#print(now)

ans1 = ans + abs(now)

ans = 0
used = set()
now = 0
i = 0
j = 0

while used != set(range(n)):
	while r_sort[j][2] in used:
		j += 1
	if not (r_sort[j][0] <= now and now <= r_sort[j][1]):
		ans += abs(now - r_sort[j][1])
		now = r_sort[j][1]
	used.add(r_sort[j][2])
	j += 1
	#print(now)
	if used == set(range(n)):
		break
	while l_sort[i][2] in used:
		i += 1
	if not (l_sort[i][0] <= now and now <= l_sort[i][1]):
		ans += abs(now - l_sort[i][0])
		now = l_sort[i][0]
	used.add(l_sort[i][2])
	i += 1
	#print(now)

ans2 = ans + abs(now)

#print(ans1, ans2)
print(max(ans1, ans2))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

ans = 0
pos = 0
while intervals:
    max_dist = -1
    max_index = -1
    max_pos = 0
    for i, interval in enumerate(intervals):
        l, r = interval
        l_dist = abs(l - pos)
        r_dist = abs(r - pos)
        dist = 0 if l <= pos <= r else min(l_dist, r_dist)
        if max_dist < dist:
            max_dist = dist
            max_index = i
            max_pos = pos if dist == 0 else (l if l_dist < r_dist else r)
    del intervals[max_index]
    ans += max_dist
    pos = max_pos

print(ans + abs(pos))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

field1 = []
field2 = []

max_r = 0
max_l = 0

for i in range(n):
    s = list(map(int, list(input().rstrip().split())))
    if(max_r < s[0]):
        max_r = s[0]
    if(s[1] < max_l):
        max_l = s[1]
    s.append(i)
    field1.append(s)
    field2.append(s)

if(max_r >= -max_l):  # 最初の進行方向右
    target = 0
    field1.sort(key=lambda x: -x[0])
    field2.sort(key=lambda x: x[1])
else:
    target = 1
    field1.sort(key=lambda x: x[1])
    field2.sort(key=lambda x: -x[0])

move = 0
now = 0
field = 1

for i in range(n):
    if(field == 1):
        aoki = field1.pop(0)
        if(now < aoki[0] or aoki[1] < now):
            move += abs(now - aoki[target])
            now = aoki[target]
        del_key = aoki[2]
        for j in range(len(field2)):
            if(field2[j][2] == del_key):
                field2.pop(j)
                break
        field = 2

    else:
        aoki = field2.pop(0)
        if(now < aoki[0] or aoki[1] < now):
            move += abs(now - aoki[1 - target])
            now = aoki[1 - target]
        del_key = aoki[2]
        for j in range(len(field1)):
            if(field1[j][2] == del_key):
                field1.pop(j)
                break
        field = 1


print(move + abs(now))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
LR = [tuple(map(int,input().split()))for i in [None] * N]
Lmin = sorted(LR,key=lambda x:x[0])
Rmax = sorted(LR,key=lambda x:x[1],reverse=True)

T = 0
def t_len(lr):
    a = lr[1] - T
    b = T - lr[0]
    return  a if a > b else b

def select(l):
    return sorted(l,key=t_len,reverse=True)[0]

def select2(l):
    a = abs(Lmin[0][0] - T)
    b = abs(Rmax[0][1] - T)
    return Lmin[0] if a > b else Rmax[0]

def selectT(lr):
    if lr[0] <= T <= lr[1]:
        return T
    a = lr[1] - T
    b = T - lr[0]
    return  lr[0] if a > b else lr[1]
K = 0
for i in [None]*N:
    s = select2(LR)
    nextT = selectT(s)
    K += abs(nextT-T)
    T = nextT
    LR.remove(s)
    Lmin.remove(s)
    Rmax.remove(s)
K += abs(T)
print(K)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
LR = [tuple(map(int,input().split()))for i in [None] * N]
T = 0
def t_len(lr):
    a = lr[1] - T
    b = T - lr[0]
    return  a if a > b else b

def select(l):
    return sorted(l,key=t_len,reverse=True)[0]

def selectT(lr):
    if lr[0] <= T <= lr[1]:
        return T
    a = lr[1] - T
    b = T - lr[0]
    return  lr[0] if a > b else lr[1]
K = 0
for i in [None]*N:
    s = select(LR)
    nextT = selectT(s)
    K += abs(nextT-T)
    T = nextT
    LR.remove(s)
K += abs(T)
print(K)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

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

    R = [(0, 0)]
    for _ in range(N):
        l, r = [int(e) for e in input().split(' ')]
        R.append((l, r))

    R.append((0, 0))

    P = [0]
    value = 0
    for i in range(1, N + 2):
        p = P[-1]
        l, r = R[i]
        if l <= p <= r:
            P.append(p)
            continue

        ld = abs(l - p)
        rd = abs(r - p)
        if ld <= rd:
            P.append(l)
            value += ld
        else:
            P.append(r)
            value += rd

    changed = True
    while changed:
        changed = False

        for i in range(1, N + 1):
            for j in range(i + 1, N + 1):
                if i + 1 == j:
                    p0 = P[i - 1]
                    p1 = P[i]
                    p2 = P[i + 1]
                    p3 = P[i + 2]

                    pv = abs(p1 - p0) + abs(p2 - p1) + abs(p3 - p2)

                    l1, r1 = R[j]
                    l2, r2 = R[i]

                    if l1 <= p0 <= r1:
                        q1 = p0
                    else:
                        ld = abs(l1 - p0)
                        rd = abs(r1 - p0)
                        if ld <= rd:
                            q1 = l1
                        else:
                            q1 = r1

                    if l2 <= q1 <= r2:
                        q2 = q1
                    else:
                        ld = abs(l2 - q1)
                        rd = abs(r2 - q1)
                        if ld <= rd:
                            q2 = l2
                        else:
                            q2 = r2

                    qv = abs(q1 - p0) + abs(q2 - q1) + abs(p3 - q2)
                else:
                    p0 = P[i - 1]
                    p1 = P[i]
                    p2 = P[i + 1]
                    p3 = P[j - 1]
                    p4 = P[j]
                    p5 = P[j + 1]

                    pv = (abs(p1 - p0) + abs(p2 - p1)
                          + abs(p4 - p3) + abs(p5 - p4))

                    l1, r1 = R[j]
                    l2, r2 = R[i]

                    if l1 <= p0 <= r1:
                        q1 = p0
                    else:
                        ld = abs(l1 - p0)
                        rd = abs(r1 - p0)
                        if ld <= rd:
                            q1 = l1
                        else:
                            q1 = r1

                    if l2 <= p3 <= r2:
                        q4 = p3
                    else:
                        ld = abs(l2 - p3)
                        rd = abs(r2 - p3)
                        if ld <= rd:
                            q4 = l2
                        else:
                            q4 = r2

                    qv = (abs(q1 - p0) + abs(p2 - q1)
                          + abs(q4 - p3) + abs(p5 - q4))

                if pv < qv:
                    P[j], P[i] = P[i], P[j]
                    R[j], R[i] = R[i], R[j]
                    value += qv - pv
                    changed = True

    print(value)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N =int(input())
ku=[]
for i in range(N):
    ku.append(list(map(int,input().split())))

K = 0
now=0
for i in range(N):
    a = np.zeros(len(ku))
    flag=[]
    for j in range(len(ku)):
        if now > ku[j][0] and now < ku[j][1]:
            a[j] = 0
            flag.append(0)
        elif now < ku[j][0]:
            a[j] = abs(now - ku[j][0])
            flag.append(1)
        else:
            a[j] = abs(now - ku[j][1])
            flag.append(2)
    idx = a.argmax()
    K += a[idx]

    if flag[idx] == 1:
        now = ku[idx][0]
    elif flag[idx] == 2:
        now = ku[idx][1]
    del ku[idx]

K+=abs(now)
print(int(K))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
lis = []
li = []
for i in range(n):
    a,b = map(int,input().split())
    li.append(a)
    lis.append(b)
cou = 0
ans = 0
co = 0
now = 0

for k in range(int(math.floor(n/2))):
    ans += max(li)-now
    now = max(li)
    lis[li.index(max(li))] = 10 ** 6
    li[li.index(max(li))] = -(10 ** 6)

      # print(k+1,li,lis,ans,now)

    ans += abs(min(lis)-now)
    now = min(lis)
    li[lis.index(min(lis))] = -(10 ** 6)
    lis[lis.index(min(lis))] = 10 ** 6

      # print(k+1,li,lis,ans,now)
if n % 2 == 0:
    ans += abs(now)
    now = 0
    print(ans)
    exit()
else:
    if now < max(li):
        ans += abs(max(li) - now) * 2
    ans += abs(now)
    now = 0
    #right = min(lis)
    #left = max(li)
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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