Problem:


Score : 700 points

Problem Statement

Takahashi and Aoki will play a game with a number line and some segments.
Takahashi is standing on the number line and he is initially at coordinate 0.
Aoki has N segments. The i-th segment is [L_i,R_i], that is, a segment consisting of points with coordinates between L_i and R_i (inclusive).

The game has N steps. The i-th step proceeds as follows:

First, Aoki chooses a segment that is still not chosen yet from the N segments and tells it to Takahashi.

Then, Takahashi walks along the number line to some point within the segment chosen by Aoki this time.

After N steps are performed, Takahashi will return to coordinate 0 and the game ends.

Let K be the total distance traveled by Takahashi throughout the game. Aoki will choose segments so that K will be as large as possible, and Takahashi walks along the line so that K will be as small as possible. What will be the value of K in the end?

Constraints

1 ≤ N ≤ 10^5

-10^5 ≤ L_i < R_i ≤ 10^5

L_i and R_i are integers.

Input

Input is given from Standard Input in the following format:

N
L_1 R_1
:
L_N R_N

Output

Print the total distance traveled by Takahashi throughout the game when Takahashi and Aoki acts as above.
It is guaranteed that K is always an integer when L_i,R_i are integers.

Sample Input 1

3
-5 1
3 7
-4 -2

Sample Output 1

10

One possible sequence of actions of Takahashi and Aoki is as follows:

Aoki chooses the first segment. Takahashi moves from coordinate 0 to -4, covering a distance of 4.

Aoki chooses the third segment. Takahashi stays at coordinate -4.

Aoki chooses the second segment. Takahashi moves from coordinate -4 to 3, covering a distance of 7.

Takahashi moves from coordinate 3 to 0, covering a distance of 3.

The distance covered by Takahashi here is 14 (because Takahashi didn't move optimally).
It turns out that if both players move optimally, the distance covered by Takahashi will be 10.

Sample Input 2

3
1 2
3 4
5 6

Sample Output 2

12

Sample Input 3

5
-2 0
-2 0
7 8
9 10
-2 -1

Sample Output 3

34



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


Sample output:
10

Submission status: Accepted

Solution code:
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 == 1 and (len(l) > 0):
    t = l[-1]
    y = a[l.pop()][1]
    while vis[t]:
      t = l.pop()
      y = a[t][1]
      vis[t] = 1
      if len(l) == 0: break
    vis[t] = 1
    if not x in range(a[t][0], a[t][1]):
      res += x - min(x, y)
      x = min(x, y)
  elif i % 2 == 0 and (len(r) > 0):
    t = r[-1]
    y = a[r.pop()][0]
    while vis[t]:
      t = r.pop()
      y = a[t][0]
      vis[t] = 1
      if len(r) == 0: break
    vis[t] = 1
    if not x in range(a[t][0], a[t][1]):
      res += max(x, y) - x
      x = max(x, y)
res += abs(x)
#print(res)
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: Accepted

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

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

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

    print(max(tot,tot2))




if __name__ == "__main__":
    main()

Submission status: Accepted

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 = max(calc(left, right), calc(left_inv, right_inv))
print(ans)

Submission status: Accepted

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


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


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

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

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
# ref https://atcoder.jp/contests/agc025/submissions/2609185
def main():
    n = int(input())
    L, R = [0], [0]
    for i in range(n):
        l, r = map(int, input().split())
        L.append(l)
        R.append(r)
    L.sort()
    L.reverse()
    R.sort()

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

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

Submission status: Accepted

Solution code:
# ref https://atcoder.jp/contests/agc025/submissions/7307839
import numpy as np

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

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

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

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

Submission status: Accepted

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

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


hq_left = []
hq_right = []

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

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

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

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

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

ans += abs(now)

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

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

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

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

ans2 += abs(now)


print(max(ans,ans2))

Submission status: Accepted

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

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

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

print(2 * ans)

Submission status: Accepted

Solution code:
import heapq

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

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

test1=ans+abs(pos)

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

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

Submission status: Accepted

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

Submission status: Accepted

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


main()

Submission status: Accepted

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

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

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

ans = 0
tmp = 0

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:

N = int(input())

L = []
R = []

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

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

ans = 0

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

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

print (ans)

Submission status: Accepted

Solution code:

"""

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

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

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

"""
import heapq

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

N = int(input())

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

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

for i in range(N):

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

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

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

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


ans = 0
now = 10**5+1

for i in range(N):

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

    if R_in_left >= L_in_right: #左にあるRに移動

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

        if len(rq) == 0:
            break

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

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

        if nexp >= now:
            break

        ans += now - nexp
        now = nexp

    else:

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

        if len(lq) == 0:
            break

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

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

        if nexp <= now:
            break

        ans += nexp - now
        now = nexp

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

print (ans)

Submission status: Accepted

Solution code:
from operator import itemgetter


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


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

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

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

Submission status: Accepted

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

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

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

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

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

ans += abs(now)

print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

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

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

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

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

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

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

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

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

print(max(a1, a2))

Submission status: Accepted

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

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

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

    ans1 += abs(prev)

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

    ans2 += abs(prev)

    print(max(ans1, ans2))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

import numpy as np

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

# 両方とるものは自明に最適にならない。よって独立に考えられる
L.sort(); L = L[::-1]
R.sort()
Lcum = L.cumsum()
Rcum = R.cumsum()

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python

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

sys.setrecursionlimit(1000000)

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

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

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

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

print ans

Submission status: Accepted

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