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: Runtime Error

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

Submission status: Runtime Error

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:
    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)
  else:
    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:
    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)
  else:
    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: Runtime Error

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):
  if i % 2:
    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)
  else:
    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):
  if i % 2 == 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)
  else:
    t = r[-1]
    y = a[r.pop()][1]
    while vis[t]:
      t = r.pop()
      y = a[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: Runtime Error

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):
  if i % 2:
    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
    res += x - min(x, y)
    x = min(x, y)
  else:
    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
    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):
  if i % 2 == 0:
    t = l[-1]
    y = a[l.pop()][1]
    while vis[l[-1]]:
      t = l.pop()
      y = a[t][1]
      vis[t] = 1
      if len(l) == 0: break
    vis[t] = 1
    rres += x - min(x, y)
    x = min(x, y)
  else:
    t = r[-1]
    y = a[r.pop()][1]
    while vis[r[-1]]:
      t = r.pop()
      y = a[t][1]
      if len(r) == 0: break
    vis[t] = 1
    rres += max(x, y) - x
    x = max(x, y)
rres += abs(x)
print(max(res, rres))

Submission status: Runtime Error

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

@stop_watch
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: Runtime Error

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

Submission status: Runtime Error

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

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

print(sum(it()))

Submission status: Runtime Error

Solution code:
def main():
    
    #0 input
    N = int(input())
    LR = []
    for i in range(N):
        LR.append(list(map(int, input().split())))
    

    
    LR_sorted_tmp = sorted(LR, reverse=False)
    LR_sorted = []
    for part in LR_sorted_tmp:
        if part[0] > 0:
            LR_sorted.append(part)

    LR_sorted_R = sorted(LR, key=lambda x:x[1], reverse=True)
    LR_sorted_R_tmp = []
    for part in LR_sorted_R_tmp:
        if part[0] < 0:
            LR_sorted_R.append(part)
    
    takahashi = 0
    moved = 0

    while 1:
        #1 choose maximum L
        next_interval  = LR_sorted[-1]
        
        # finish if Takahashi is in the next interval
        if next_interval[0] <= takahashi and takahashi <= next_interval[1]:
            break
        
        moved += next_interval[0] - takahashi
        takahashi = next_interval[0]
        
        # delete the current interval
        del LR_sorted[-1]

        # finish if no items in the list
        if len(LR_sorted) == 0:
            break


        
        #2 choose minimum R      
        next_interval = LR_sorted_R[-1]
        
        # finish if Takahashi is in the next interval
        if next_interval[0] <= takahashi and takahashi <= next_interval[1]:
            break
        
        moved += takahashi - next_interval[1]
        takahashi = next_interval[1]
        
        # delete the current interval
        del LR_sorted_R[-1]


        # finish if no items in the list
        if len(LR_sorted) == 0:
            break
        
        
    moved += abs(0-takahashi)
    print(moved)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    
    #0 input
    N = int(input())
    LR = []
    for i in range(N):
        LR.append(list(map(int, input().split())))
    

    
    LR_sorted_tmp = sorted(LR, reverse=False)
    LR_sorted = []
    for part in LR_sorted_tmp:
        if part[0] > 0:
            LR_sorted.append(part)

    LR_sorted_R = sorted(LR, key=lambda x:x[1], reverse=True)
    LR_sorted_R_tmp = []
    for part in LR_sorted_R_tmp:
        if part[0] < 0:
            LR_sorted_R.append(part)
    
    takahashi = 0
    moved = 0

    while 1:
        #1 choose maximum L
        next_interval  = LR_sorted[-1]
        
        # finish if Takahashi is in the next interval
        if next_interval[0] <= takahashi and takahashi <= next_interval[1]:
            break
        
        moved += next_interval[0] - takahashi
        takahashi = next_interval[0]
        
        # delete the current interval
        del LR_sorted[-1]

        # finish if no items in the list
        if len(LR_sorted) == 0:
            break


        
        #2 choose minimum R      
        next_interval = LR_sorted_R[-1]
        
        # finish if Takahashi is in the next interval
        if next_interval[0] <= takahashi and takahashi <= next_interval[1]:
            break
        
        moved += takahashi - next_interval[1]
        takahashi = next_interval[1]
        
        # delete the current interval
        del LR_sorted_R[-1]


        # finish if no items in the list
        if len(LR_sorted) == 0:
            break
        
        
    moved += abs(0-takahashi)
    print(moved)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
import math
from collections import deque
n = int(input())
lis = deque()
li = deque()
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.remove(lis[li.index(max(li))])
    li.remove(li[li.index(max(li))])
      # print(k+1,li,lis,ans,now)
    ans += abs(min(lis)-now)
    now = min(lis)
    li.remove(li[lis.index(min(lis))])
    lis.remove(lis[lis.index(min(lis))])
      # 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: Runtime Error

Solution code:
def combo(m,n):
    ans=1
    for i in range(n+1,m+1):
        ans*=i
    for i in range(1,(m-n+1)):
        ans=ans//i
    return ans

num=input().split()
N=int(num[0])
A=int(num[1])
B=int(num[2])
K=int(num[3])
res=0
tim=min(K//A,N)

for i in range(0,min(tim+1)):
    if (K-i*A)%B==0:
        m=i
        n=(K-i*A)//B
        if m+n>2*N:
            continue
        for j in range(0,min(m+1,n+1)):
            if m+n-j>N:
                continue
            # print(j,m-j,n-i)
            res=res+combo(N,j)*combo(N-j,m-j)*combo(N-m,n-j)
            res=res%998244353
print(res)

Submission status: Runtime Error

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
if print(ans+abs(now))