Problem p02874 (python)

Fixed submission:
import sys
from itertools import accumulate
N,*L = map(int, open(0).read().split())
ls = [0]*N
ml = -1
nr = -1
li = -1
mr = 10**9
nl = -1
ri = -1
for i,(a,b) in enumerate(zip(*[iter(L)]*2)):
  ls[i] = a,b
  if ml<a:
    ml = a
    nr = b
    li = i
  if b<mr:
    mr = b
    nl = a
    ri = i

if ri!=li:
  a,b = min(li,ri),max(li,ri)
  ls.pop(b)
  ls.pop(a)
  N -= 2
else:
  ls.pop(li)
  N -= 1
if N==0:
  ans = max(mr-nl+1,0)+max(nr-ml+1,0)
  print(ans)
  sys.exit()
ls.sort()
length = max(c[1]-c[0]+1 for c in ls)
ans = max(mr-ml+1,0)+length
r = list(accumulate((c[1] for c in ls[::-1]), min))[::-1]
l = list(c[0] for c in ls)
ans = max(ans, max(mr-nl+1,0)+max(r[0]-ml+1,0))
for i in range(N-1):
  xl = max(nl,l[i])
  xr = min(nr,r[i+1])
  ans = max(ans, max(mr-xl+1,0)+max(xr-ml+1,0))
xl = max(nl,l[N-1])
ans = max(ans, max(mr-xl+1,0)+nr-ml+1)
print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
N,*L = map(int, open(0).read().split())
ls = [0]*N
ml = -1
nr = -1
li = -1
mr = 10**9
nl = -1
ri = -1
length = 0
for i,(a,b) in enumerate(zip(*[iter(L)]*2)):
  ls[i] = a,b
  if ml<a:
    ml = a
    nr = b
    li = i
  if b<mr:
    mr = b
    nl = a
    ri = i
  length = max(length, b-a+1)

ans = max(mr-ml+1,0)+length
if ri!=li:
  a,b = min(li,ri),max(li,ri)
  ls.pop(b)
  ls.pop(a)
  N -= 2
else:
  ls.pop(li)
  N -= 1
ls.sort()
r = list(accumulate((c[1] for c in ls[::-1]), min))[::-1]
l = list(c[0] for c in ls)
ans = max(ans, max(mr-nl+1,0)+max(r[0]-ml+1,0))
for i in range(N-1):
  xl = max(nl,l[i])
  xr = min(nr,r[i+1])
  ans = max(ans, max(mr-xl+1,0)+max(xr-ml+1,0))
xl = max(nl,l[N-1])
ans = max(ans, max(mr-xl+1,0)+nr-ml+1)
print(ans)

Buggy submission (verdict: Runtime Error):
N, *L = map(int, open('0').read().split())
inf = []
ls = []
rs = []
fl = 0
fr = float('inf')
for i,x in enumerate(zip(*[iter(L)]*2)):
  l,r = x
  ls.append((l,i))
  rs.append((r,i))
  inf.append((l,r))
ls.sort()
rs.sort(reverse=True)
m = 0
used = [False]*N
l1 = -1
l2 = -2
r1 = -1
r2 = -2
while True:
  while l1>=-N:
    i = ls[l1][1]
    if not used[i]:
      break
    l1 -= 1
  else:
    break
  while r1>=-N:
    i = rs[r1][1]
    if not used[i]:
      break
    r1 -= 1
  else:
    break
  while l2>=-N:
    i = ls[l2][1]
    if (not used[i]) and l1>l2:
      break
    l2 -= 1
  else:
    break
  while r2>=-N:
    i = rs[r2][1]
    if (not used[i]) and r1>r2:
      break
    r2 -= 1
  else:
    break
  x = rs[r1][0]-ls[l1][0]+1
  fa = m+x
  
  ll, i = ls[l1]
  rr, j= rs[r1]
  if i==j:
    lr = inf[i][1]
    a,b = max(ll,fl),min(lr,fr)
    p,q = a,b
    lm = b-a+1
    lx = rs[r1][0]-ls[l2][0]+1
    la = lm+lx
    rm = lm
    ra = la
  else:
    lr = inf[i][1]
    a = max(ll,fl)
    b = min(lr,fr)
    lm = b-a+1
    lx = rs[r1][0]-ls[l2][0]+1
    la = lm+lx
  
    rl = inf[j][0]
    p = max(rl,fl)
    q = min(rr,fr)
    rm = q-p+1
    rx = rs[r2][0]-ls[l1][0]+1
    ra = rm+rx
  if la>ra:
    if la>fa:
      fl = a
      fr = b
      m = lm
      used[i] = True
    else:
      break
  else:
    if ra>fa:
      fl = p
      fr = q
      m = rm
      used[j] = True
    else:
      break
first = [0,float('inf')]
second = [0,float('inf')]
for i,flag in enumerate(used):
  if flag:
    first[0] = max(first[0], inf[i][0])
    first[1] = min(first[1], inf[i][1])
  else:
    second[0] = max(second[0], inf[i][0])
    second[1] = min(second[1], inf[i][1])
if float('inf') in first or float('inf') in second:
  print(0)
else:
  ans = first[1]-first[0]+1 + second[1]-second[0]+1
  print(max(0,ans))