Problem p03559 (python)

Fixed submission:
def main(n,a,b,c):
  import bisect
  ans=0
  for i in range(n):
    na=bisect.bisect_left(a,b[i])
    nc=n-bisect.bisect_right(c,b[i])
    ans+=na*nc
  print(ans)
if __name__=='__main__':
  n=int(input())
  a=sorted(list(map(int,input().split())))
  b=sorted(list(map(int,input().split())))
  c=sorted(list(map(int,input().split())))
  main(n,a,b,c)

Buggy submission (verdict: Runtime Error):
def main(n,a,b,c):
  import bisect
  ans=0
  todo=[[ai] for ai in a]
  while len(todo)>0:
    d=todo.pop()
    if len(d)==1:
      l=bisect.bisect_right(b,d[-1])
      for li in b[l:]:
        e=d.copy()
        e.append(li)
        todo.append(e)
    elif len(d)==2:
      l=bisect.bisect_right(c,d[-1])
      for li in c[l:]:
        e=d.copy()
        e.append(li)
        todo.append(e)
    elif len(d)==3:
      ans+=1
  print(ans)
if __name__=='__main__':
  n=int(input())
  a=sorted(list(map(int,input().split())))
  b=sorted(list(map(int,input().split())))
  c=sorted(list(map(int,input().split())))
  main(n,a,b,c)

Buggy submission (verdict: Runtime Error):
def main(n,a,b,c):
  import bisect
  ans=0
  todo=[[ai] for ai in a]
  while len(todo)>0:
    d=todo.pop()
    if len(d)==1:
      l=bisect.bisect_right(b,d[-1])
      for li in b[l:]:
        e=d.copy()
        e.append(li)
        todo.append(e)
    if len(d)==2:
      l=bisect.bisect_right(c,d[-1])
      for li in c[l:]:
        e=d.copy()
        e.append(li)
        todo.append(e)
    if len(d)==3:
      ans+=1
  print(ans)
if __name__=='__main__':
  n=int(input())
  a=sorted(list(map(int,input().split())))
  b=sorted(list(map(int,input().split())))
  c=sorted(list(map(int,input().split())))
  main(n,a,b,c)

Buggy submission (verdict: Runtime Error):
def main(n,a,b,c):
  import bisect
  ab=[] #ab[i]:上部にi個目を選んだ時、中部に選べるもののうち最小のインデックス。選べないならnになる
  ab.append(bisect.bisect_right(b,a[0]))
  bc=[]
  bc.append(bisect.bisect_right(c,b[0]))
  for i in range(1,n):
    if a[i]<b[ab[i-1]]:
      ab.append(ab[i-1])
    else:
      ab.append(bisect.bisect_right(b[ab[i-1]:],a[i])+ab[i-1])
    if b[i]<c[bc[i-1]]:
      bc.append(bc[i-1])
    else:
      bc.append(bisect.bisect_right(c[bc[i-1]:],b[i])+bc[i-1])
  ans=0
  for i in range(n):
    for j in range(ab[i],n):
      ans+=n-bc[j]
  print(ans)
if __name__=='__main__':
  n=int(input())
  a=sorted(list(map(int,input().split())))
  b=sorted(list(map(int,input().split())))
  c=sorted(list(map(int,input().split())))
  main(n,a,b,c)

Buggy submission (verdict: Runtime Error):
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ab={} #ab[i]:上部にi個目を選んだ時、中部に選べるもののうち最小のインデックス。選べないならnになる
l=bisect.bisect_right(b,a[0])
ab[0]=l
for i in range(1,n):
  if a[i]<b[ab[i-1]]:
    ab[i]=ab[i-1]
  else:
    j=ab[i-1]+1
    while n>j and a[i]>=b[j]:
      j+=1
    ab[i]=j
bc={} 
l=bisect.bisect_right(c,b[0])
bc[0]=l
for i in range(1,n):
  if b[i]<c[bc[i-1]]:
    bc[i]=bc[i-1]
  else:
    j=bc[i-1]+1
    while n>j and b[i]>=c[j]:
      j+=1
    bc[i]=j
ans=0
for i in range(n):
  for j in range(ab[i],n):
    ans+=n-bc[j]
print(ans)

Buggy submission (verdict: Runtime Error):
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ab={} #ab[i]:上部にi個目を選んだ時、中部に選べるもののうち最小のインデックス。選べないならnになる
l=bisect.bisect_right(b,a[0])
ab[0]=l
for i in range(1,n):
  if a[i]<b[ab[i-1]]:
    ab[i]=ab[i-1]
  else:
    j=ab[i-1]+1
    while n>j and a[i]>=b[j]:
      j+=1
    ab[i]=j
bc={} 
l=bisect.bisect_right(c,b[0])
bc[0]=l
for i in range(1,n):
  if b[i]<c[bc[i-1]]:
    bc[i]=bc[i-1]
  else:
    j=bc[i-1]+1
    while n>j and b[i]>=c[j]:
      j+=1
    bc[i]=j
ans=0
for i in range(n):
  for j in range(ab[i],n):
    ans+=n-bc[j]