Problem:


Score : 300 points

Problem Statement

The season for Snuke Festival has come again this year. First of all, Ringo will perform a ritual to summon Snuke. For the ritual, he needs an altar, which consists of three parts, one in each of the three categories: upper, middle and lower.

He has N parts for each of the three categories. The size of the i-th upper part is A_i, the size of the i-th middle part is B_i, and the size of the i-th lower part is C_i.

To build an altar, the size of the middle part must be strictly greater than that of the upper part, and the size of the lower part must be strictly greater than that of the middle part. On the other hand, any three parts that satisfy these conditions can be combined to form an altar.

How many different altars can Ringo build? Here, two altars are considered different when at least one of the three parts used is different.

Constraints

1 \leq N \leq 10^5

1 \leq A_i \leq 10^9(1\leq i\leq N)

1 \leq B_i \leq 10^9(1\leq i\leq N)

1 \leq C_i \leq 10^9(1\leq i\leq N)

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N
B_1 ... B_N
C_1 ... C_N

Output

Print the number of different altars that Ringo can build.

Sample Input 1

2
1 5
2 4
3 6

Sample Output 1

3

The following three altars can be built:

Upper: 1-st part, Middle: 1-st part, Lower: 1-st part

Upper: 1-st part, Middle: 1-st part, Lower: 2-nd part

Upper: 1-st part, Middle: 2-nd part, Lower: 2-nd part

Sample Input 2

3
1 1 1
2 2 2
3 3 3

Sample Output 2

27

Sample Input 3

6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288

Sample Output 3

87



Sample input:
2
1 5
2 4
3 6


Sample output:
3

Submission status: Runtime Error

Solution code:
icase=0
if icase==0:
    n=int(input())  #数値入力 「N」だけの入力のとき
    a=[]
    b=[]
    c=[]
    for i in range(n):
       ai,bi,ci=map(int, input().split())
       a.append(ai)
       b.append(bi)
       c.append(ci)
elif icase==1:
    n=2
    a=[1,5]
    b=[2,4]
    c=[3,6]
elif icase==2:
    n=6
    a=[3, 14, 159, 2, 6, 53]
    b=[58, 9, 79, 323, 84, 6]
    c=[2643, 383, 2, 79, 50, 288]
    
a.sort()
b.sort()
c.sort()
   
icnt=0
ast=0
cst=0
for i in range(n):
    if a[n-1]<=b[i]:
        ast=n
#        print("a1:",ast-1,a[ast-1],i,b[i])
    else:
        while a[ast]<b[i] and ast<n-1:
            ast=ast+1
#            print("a2:",ast-1,a[ast-1],i,b[i])
    if b[i]<c[0]:
        cst=0 
#        print("c1:",cst,c[cst],i,b[i])
    else:
        while b[i]>=c[cst] and cst<n-1:
            cst=cst+1
#            print("c2:",cst-1,c[cst-1],i,b[i])
#    print(ast,i,n-cst)
    icnt=icnt+(ast)*(n-cst)
    
print(icnt)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ab = [0] * (max(a) + 1)
bc = [0] * (max(b) + 1)

def isok(na , index , key):
    if na[index] >= key:
        return True
    else:
        return False
    
def bs(nar,key):
    left = -1
    right = len(nar)
    
    while (right - left) > 1:
        mid = left + (right - left) // 2
        
        if isok(nar , mid , key):
            right = mid
        else:
            left = mid
            
    return right

ans = 0
for i in b:
    q = bs(a,i)
    r = bs(c,i+1)
    
    ans += q*(n-r)
print(ans)

Submission status: Runtime Error

Solution code:
def quick_sort(arr):
 left = []
 right = []
 if len(arr) <= 1:
  return arr
 ref = arr[0]
 ref_count = 0
 for ele in arr:
  if ele < ref:
   left.append(ele)
  elif ele > ref:
   right.append(ele)
  else:
   ref_count += 1
 left = quick_sort(left)
 right = quick_sort(right)
 return left + [ref] * ref_count + right

def binary_search1(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] >= target:
   if list[center-1] < target:
    result = center
    break
   else: right = center - 1
  elif list[center] < target:
   if center==N-1:
    result = N
    break
   else:
    left = center + 1
 if result == -1:
  return 0
 else:
  return str(result)

def binary_search2(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] <= target:
   if list[center+1] > target:
    result = N-center-1
    break
   else:  left = center + 1
  elif list[center] > target:
   if center==0:
    result = N-center
    break
   else:
    right =center - 1
 if result == -1:
  return 0
 else:
  return str(result)

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A=quick_sort(A)
C=quick_sort(C)
K=0
for i in range(N):
 L=int(binary_search1(A,B[i]))
 M=int(binary_search2(C,B[i]))
 K+=L*M
print(K)

Submission status: Runtime Error

Solution code:
import os
import statistics

def quick_sort(arr):
 left = []
 right = []
 if len(arr) <= 1:
  return arr
 ref = arr[0]
 ref_count = 0
 for ele in arr:
  if ele < ref:
   left.append(ele)
  elif ele > ref:
   right.append(ele)
  else:
   ref_count += 1
 left = quick_sort(left)
 right = quick_sort(right)
 return left + [ref] * ref_count + right

def binary_search1(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] >= target:
   if list[center-1] < target:
    result = center
    break
   else: right = center - 1
  elif list[center] < target:
   if center==N-1:
    result = N
    break
   else:
    left = center + 1
 if result == -1:
  return 0
 else:
  return str(result)

def binary_search2(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] <= target:
   if list[center+1] > target:
    result = N-center-1
    break
   else:  left = center + 1
  elif list[center] > target:
   if center==0:
    result = N-center
    break
   else:
    right =center - 1
 if result == -1:
  return 0
 else:
  return str(result)

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A=quick_sort(A)
C=quick_sort(C)
K=0
for i in range(N):
 L=int(binary_search1(A,B[i]))
 M=int(binary_search2(C,B[i]))
 K+=L*M
print(K)

Submission status: Runtime Error

Solution code:
import os
import statistics

def quickSort(arr):
  left = []
  right = []
  if len(arr) <= 1:
   return arr
  median = int(statistics.median(arr))
  medianFlg = 0
  for element in arr:
   if element < median:
    left.append(element)
   elif element > median:
    right.append(element)
   else:
    medianFlg += 1
  left = quickSort(left)
  right = quickSort(right)
  return left + [median] * medianFlg + right

def binary_search1(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] >= target:
   if list[center-1] < target:
    result = center
    break
   else: right = center - 1
  elif list[center] < target:
   if center==N-1:
    result = N
    break
   else:
    left = center + 1
 if result == -1:
  return 0
 else:
  return str(result)

def binary_search2(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] <= target:
   if list[center+1] > target:
    result = N-center-1
    break
   else:  left = center + 1
  elif list[center] > target:
   if center==0:
    result = N-center
    break
   else:
    right =center - 1
 if result == -1:
  return 0
 else:
  return str(result)

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A=quickSort(A)
C=quickSort(C)
K=0
for i in range(N):
 L=int(binary_search1(A,B[i]))
 M=int(binary_search2(C,B[i]))
 K+=L*M
print(K)

Submission status: Runtime Error

Solution code:
import os
import statistics

def quickSort(arr):
  left = []
  right = []
  if len(arr) <= 1:
   return arr
  median = int(statistics.median(arr))
  medianFlg = 0
  for element in arr:
   if element < median:
    left.append(element)
   elif element > median:
    right.append(element)
   else:
    medianFlg += 1
  left = quickSort(left)
  right = quickSort(right)
  return left + [median] * medianFlg + right

def binary_search1(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] >= target:
   if list[center-1] < target:
    result = center
    break
   else: right = center - 1
  elif list[center] < target:
   if center==N-1:
    result = N
    break
   else:
    left = center + 1
 if result == -1:
  return 0
 else:
  return str(result)

def binary_search2(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] <= target:
   if list[center+1] > target:
    result = N-center-1
    break
   else:  left = center + 1
  elif list[center] > target:
   if center==0:
    result = N-center
    break
   else:
    right =center - 1
 if result == -1:
  return 0
 else:
  return str(result)

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A=quickSort(A)
C=quickSort(C)
K=0
for i in range(N):
 L=int(binary_search1(A,B[i]))
 M=int(binary_search2(C,B[i]))
 K+=L*M
print(K)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
i,j,k=0
ans=0
while i<n and j<n and k<n:
  while j<n and a[i]>=b[j]:
    j+=1
  if j==n:
    break
  while k<n and b[j]>=c[k]:
    k+=1
  if k==n:
    break
  ans+=1
  i+=1
  j+=1
  k+=1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
i,j,k=0
ans+=1
while i<n and j<n and k<n:
  while j<n and a[i]>=b[j]:
    j+=1
  if j==n:
    break
  while k<n and b[j]>=c[k]:
    k+=1
  if k==n:
    break
  ans+=1
  i+=1
  j+=1
  k+=1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
i,j,k=0
ans+=1
while i<n and j<n and k<n:
  while j<n and a[i]>=b[j]:
    j+=1
  while k<n and b[j]>=c[k]:
    k+=1
  ans+=1
  i+=1
  j+=1
  k+=1
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect
N=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
B_reverse=B[::-1]
C=sorted(list(map(int,input().split())))
cnt=0
dict={}
val=0
for b in B_reverse:
    c_min=bisect(C,b)
    val+=len(C[c_min:])
    dict[b]=val
for a in A:
    cnt+=dict[B[bisect(B,a)]]
print(cnt)

Submission status: Runtime Error

Solution code:
#20　AtCoder Beginner Contest 077 C - Snuke Festival
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
c.sort()
ans = 0
for i in b:
    if i <= a[n-1]: lena=len(a[:bisect.bisect_left(a, i)])
    else: lena=n
    if i+1<= c[n-1]: lenc=len(a[bisect.bisect_left(c, i+1):])
    ans += lena*lenc
print(ans)

Submission status: Runtime Error

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

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
# print(f"N: {N}")
# print(f"A, B, C: {A}, {B}, {C}")

def binary_search_left(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return left
    if value > arr[right]:
        return right + 1
    while left <= right:
        mid = (left + right) // 2
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            # find the leftmost index
            while arr[mid] == value:
                mid -= 1
            return mid + 1
    # left == right + 1, so arr[right] < value < arr[left]
    return left

def binary_search_right(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return left
    if value > arr[right]:
        return right + 1
    while left <= right:
        mid = (left + right) // 2
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            # find the leftmost index
            while arr[mid] == value:
                if mid == len(arr) - 1:
                    return mid + 1
                mid += 1
            return mid
    # left == right + 1, so arr[right] < value < arr[left]
    return left

count = 0
for bot in B:
    # print(f"bot: {bot}")
    index_A = binary_search_left(A, bot)
    index_C = binary_search_right(C, bot)
    # print(f"index_A: {index_A}, index_C: {index_C}")
    count += index_A * (N - index_C)

print(count)

Submission status: Runtime Error

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

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
# print(f"N: {N}")
# print(f"A, B, C: {A}, {B}, {C}")

def binary_search_left(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return left
    if value > arr[right]:
        return right + 1
    while left <= right:
        mid = (left + right) // 2
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            # find the leftmost index
            while arr[mid] == value:
                mid -= 1
            return mid + 1
    # left == right + 1, so arr[right] < value < arr[left]
    return left

def binary_search_right(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return left
    if value > arr[right]:
        return right
    while left <= right:
        mid = (left + right) // 2
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            # find the leftmost index
            while arr[mid] == value:
                mid += 1
            return mid
    # left == right + 1, so arr[right] < value < arr[left]
    return left

count = 0
for bot in B:
    # print(f"bot: {bot}")
    index_A = binary_search_left(A, bot)
    index_C = binary_search_right(C, bot)
    # print(f"index_A: {index_A}, index_C: {index_C}")
    count += index_A * (N - index_C)

print(count)

Submission status: Runtime Error

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

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
# print(f"N: {N}")
print(f"A, B, C: {A}, {B}, {C}")

def binary_search_left(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return left
    if value > arr[right]:
        return right + 1
    while left <= right:
        mid = (left + right) // 2
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            # find the leftmost index
            while arr[mid] == value:
                mid -= 1
            return mid + 1
    # left == right + 1, so arr[right] < value < arr[left]
    return left

def binary_search_right(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return left
    if value > arr[right]:
        return right
    while left <= right:
        mid = (left + right) // 2
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            # find the leftmost index
            while arr[mid] == value:
                mid += 1
            return mid
    # left == right + 1, so arr[right] < value < arr[left]
    return left

count = 0
for bot in B:
    print(f"bot: {bot}")
    index_A = binary_search_left(A, bot)
    index_C = binary_search_right(C, bot)
    print(f"index_A: {index_A}, index_C: {index_C}")
    count += index_A * (N - index_C)

print(count)

Submission status: Runtime Error

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

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A)
B = sorted(B)
C = sorted(C)
# print(f"N: {N}")
# print(f"A, B, C: {A}, {B}, {C}")

def binary_search_lower_bound(arr, value):
    left = 0
    right = len(arr) - 1
    if value <= arr[left]:
        return left
    if value >= arr[right]:
        return right
    while left <= right:
        mid = int((left + right) / 2)
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            return mid
    # left == right + 1, so arr[right] < value < arr[left]
    return left

def binary_search_more_than(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return left
    if value > arr[right]:
        return None
    while left <= right:
        mid = int((left + right) / 2)
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            return mid + 1
    # left == right + 1, so arr[right] < value < arr[left]
    return left

def binary_search_less_than(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return None
    if value > arr[right]:
        return right
    while left <= right:
        mid = int((left + right) / 2)
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            return mid - 1
    # left == right + 1, so arr[right] < value < arr[left]
    return right

count = 0
for bot in B:
    index_A = binary_search_less_than(A, bot)
    index_C = binary_search_more_than(C, bot)
    # print(f"index_A: {index_A}")
    # print(f"index_C: {index_C}")
    count += (index_A + 1) * (N - index_C)

print(count)

Submission status: Runtime Error

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

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A)
B = sorted(B)
C = sorted(C)
# print(f"N: {N}")
# print(f"A, B, C: {A}, {B}, {C}")

# def binary_search_lower_bound(arr, value):
#     left = 0
#     right = len(arr) - 1
#     if value <= arr[left]:
#         return left
#     if value >= arr[right]:
#         return right
#     while left <= right:
#         mid = int((left + right) / 2)
#         if value > arr[mid]:
#             left = mid + 1
#         elif value < arr[mid]:
#             right = mid - 1
#         else:
#             return mid
#     # left == right + 1, so arr[right] < value < arr[left]
#     return left

def binary_search_more_than(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return left
    if value > arr[right]:
        return right
    while left <= right:
        mid = int((left + right) / 2)
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            return mid + 1
    # left == right + 1, so arr[right] < value < arr[left]
    return left

count = 0
alters = []
B_bin = B[:]
for top in A:
    # print(f"\ntop: {top}")
    # print(f"B, C: {B}, {C}")
    index_B = binary_search_more_than(B_bin, top)
    B_bin = B_bin[index_B:]
    # print(f"B_bin: {B_bin}")
    C_bin = C[:]
    for mid in B_bin:
        # print(f"mid: {mid}")
        index_C = binary_search_more_than(C_bin, mid)
        C_bin = C_bin[index_C:]
        # print(f"C_bin: {C_bin}")
        count += len(C_bin)

print(count)

Submission status: Runtime Error

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

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A)
B = sorted(B)
C = sorted(C)
print(f"N: {N}")
print(f"A, B, C: {A}, {B}, {C}")

# def binary_search_lower_bound(arr, value):
#     left = 0
#     right = len(arr) - 1
#     if value <= arr[left]:
#         return left
#     if value >= arr[right]:
#         return right
#     while left <= right:
#         mid = int((left + right) / 2)
#         if value > arr[mid]:
#             left = mid + 1
#         elif value < arr[mid]:
#             right = mid - 1
#         else:
#             return mid
#     # left == right + 1, so arr[right] < value < arr[left]
#     return left

def binary_search_more_than(arr, value):
    left = 0
    right = len(arr) - 1
    if value < arr[left]:
        return left
    if value > arr[right]:
        return right
    while left <= right:
        mid = int((left + right) / 2)
        if value > arr[mid]:
            left = mid + 1
        elif value < arr[mid]:
            right = mid - 1
        else:
            return mid + 1
    # left == right + 1, so arr[right] < value < arr[left]
    return left

count = 0
alters = []
for top in A:
    # print(f"\ntop: {top}")
    index_B = binary_search_more_than(B, top)
    B_bin = B[index_B:]
    # print(f"B_bin: {B_bin}")
    for mid in B_bin:
        # print(f"mid: {mid}")
        index_C = binary_search_more_than(C, mid)
        C_bin = C[index_C:]
        # print(f"C_bin: {C_bin}")
        count += len(C_bin)

print(count)

Submission status: Runtime Error

Solution code:
def binary_search(A,x,flag):
  start = 0
  end = len(A)-1
  
  while start < end:
    middle = (start + end) // 2
    if flag:# Aの時
      if A[middle] < x <= A[middle+1]:
        return middle + 1
      elif x <= A[middle]:
        end = middle
      else:
        start = middle + 1
    else:# Bの時
      if A[middle] <= x < A[middle+1]:
        return middle + 1
      elif x < A[middle]:
        end = middle
      else:
        start = middle + 1
    if end == 0: # 小さい
      return 0
    elif start == len(A)-1:
      return len(A)
        
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0

for i in range(N):
  ans += binary_search(A,B[i],True)*(N-binary_search(C,B[i],False))#B[i]より小さいAの数とB[i]より大きいCの数の積
print(ans)

Submission status: Runtime Error

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()
b = li()
c = li()

a.sort()
b.sort()
c.sort()

from bisect import bisect_right
def bisect_find(a, x):
    i = bisect_right(a, x)
    return i

# Bのメモを作る
# 任意の中段パーツが乗ることが可能な下段パーツの数をあらかじめ計算しておく
# その後、任意の中段パーツ以上の中段パーツが選択できる下段パーツの数を累積和で求める
b_memo = [0]*n
for i in range(n):
    c_min_limit = bisect_find(c,i)
    b_memo[i] =  len(c[c_min_limit:])

b_cumsum = [b_memo[n-1]]
for i in range(n-1):
    b_cumsum.append(b_cumsum[i] + b_memo[n-2-i])

b_cumsum.reverse()

ans = 0
for i in a:
    b_min_limit = bisect_find(b, i)
    ans += b_cumsum[b_min_limit]
    
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for i in range(n):
    x = bisect.bisect_left(a, b[i])
    y = bisect.bisect_right(c, b[i])
    ans += x * (n - y)
print(ans)

Submission status: Runtime Error

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


def count_over_target(lst, target):
    ng = -1
    ok = len(lst)
    while abs(ok-ng) > 1:
        mid = (ok+ng) // 2
        if lst[mid] > target:
            ok = mid
        else:
            ng = mid
    if lst[ok] == target:
        return len(lst[ok:]) - 1
    return len(lst[ok:])


def main():
    _ = int(input())
    a = sorted(list(map(int, input().split())))
    b = list(map(int, input().split()))
    c = sorted(list(map(int, input().split())))
    # print("a:", a)
    # print("c:", c)
    num_a = len(a)
    ans = 0
    for i in b:
        # print("b:", i)
        under = num_a - count_over_target(a, i)
        # print("under:", under)
        over = count_over_target(c, i)
        # print("over:", over)
        ans += under * over
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
# サイズが下の方が大きくないとダメtop<mid<bottom
tops = sorted(list(map(int, input().split(" "))))
mids = sorted(list(map(int, input().split(" "))))
bottoms = sorted(list(map(int, input().split(" "))))


def binary_search(check_list, num, left, right):
    if left > right:
        return left
    mid = (left + right) // 2
    if check_list[mid] > num:
        return binary_search(check_list, num, left, mid - 1)
    elif check_list[mid] == num:
        return mid
    else:
        return binary_search(check_list, num, mid + 1, right)


total_count = 0
for bottom in bottoms:
    mid_insert_index = binary_search(mids, bottom, 0, N - 1)

    for mid in mids[0:mid_insert_index]:
        top_insert_index = binary_search(tops, mid, 0, N - 1)
        total_count += top_insert_index])
print(total_count)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

N = int(input())
A = sorted(list(map(int, input().split(" "))))
B = sorted(list(map(int, input().split(" "))))
C = sorted((map(int, input().split(" "))))


def count_more_value_elements(array, v):
    insert_index = bisect_left(array, v)
    if not insert_index > len(array) - 1:
        if C[insert_index] == b:
            return len(array) - insert_index - 1
        else:
            return len(array) - insert_index


def count_less_value_elements(array, v):
    insert_index = bisect_left(array, v)
    if not insert_index > len(array) - 1:
        if C[insert_index] == b:
            return insert_index + 1
        else:
            return insert_index
    else:
        return insert_index


count = 0
for b in B:
    a_poss = count_less_value_elements(A, b)
    c_poss = count_more_value_elements(C, b)
    count += a_poss*c_poss

print(count)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

N = int(input())
A = sorted(list(map(int, input().split(" "))))
B = sorted(list(map(int, input().split(" "))))
C = sorted((map(int, input().split(" "))))


def count_more_value_elements(array, v):
    insert_index = bisect_left(array, v)
    if not insert_index > len(array) - 1:
        if C[insert_index] == b:
            return len(array) - insert_index - 1
        else:
            return len(array) - insert_index


def count_less_value_elements(array, v):
    insert_index = bisect_left(array, v)
    if not insert_index >= len(array) - 1:
        if C[insert_index] == b:
            return insert_index + 1
        else:
            return insert_index
    else:
        return insert_index


count = 0
for b in B:
    a_poss = count_less_value_elements(A, b)
    c_poss = count_more_value_elements(C, b)
    count += a_poss*c_poss

print(count)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

N = int(input())
A = sorted(list(map(int, input().split(" "))))
B = sorted(list(map(int, input().split(" "))))
C = sorted((map(int, input().split(" "))))

count = 0
for a in A:
    for b in B:
        if b <= a:
            continue
        insert_index = bisect_left(C, b)
        if C[insert_index] == b:
            count += len(C) - insert_index - 1
        else:
            count += len(C) - insert_index

print(count)

Submission status: Runtime Error

Solution code:
import sys
import bisect

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
c = list(map(int, sys.stdin.readline().split()))

a.sort()
b.sort()
c.sort()

b_ans_list = [0 for _ in range(n)]
for i in reversed(range(n)):
    # b[i]における選択可能なcの個数
    if i == n-1:
        b_ans_list[i] = n - bisect.bisect_right(c, b[i])
    else:
        b_ans_list[i] = n - bisect.bisect_right(c, b[i]) + b_ans_list[i+1]

ans = 0
for i in range(n):
    ans += b_ans_list[bisect.bisect_right(b, a[i])]

print(ans)

Submission status: Runtime Error

Solution code:
'''
https://atcoder.jp/contests/abc077/tasks/arc084_a
'''
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A.sort()
    B.sort()
    C.sort()

    def nibu(num, l):
        L = 0
        R = n-1
        mid = (L+R)//2
        if l[L]>num:
            return n, L
        if l[R]<num:
            return 0, n
        while 1:
            if l[L]<=num and num<l[L+1]:
                return n-(L+1), L+1
            elif l[mid]<=num:
                L = mid
            else:
                R = mid
            mid = (L+R)//2
    res = 0
    for i in A:
        x, na = nibu(i, B)
        for j in B[na:]:
            y, nb = nibu(j, C)
            res += y
    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

def sunuke(ai, bi, ci, ans):

    if ai > N-1:
        print(ans)
    elif bi > N-1:
        sunuke(ai+1, 0, 0, ans)
    elif ci > N-1:
        sunuke(ai, bi+1, 0, ans)

    elif A[ai] >= B[bi]:
        sunuke(ai,bi+1,ci, ans)
    elif B[bi] >= C[ci]:
        sunuke(ai, bi, ci+1, ans)
    else:
        sunuke(ai, bi, ci+1, ans+1)

ans = 0
sunuke(0,0,0, ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

print(N,A,B,C)
def sunuke(ai, bi, ci, ans):

    if ai > N-1:
        print(ans)
    elif bi > N-1:
        sunuke(ai+1, 0, 0, ans)
    elif ci > N-1:
        sunuke(ai, bi+1, 0, ans)

    elif A[ai] >= B[bi]:
        sunuke(ai,bi+1,ci, ans)
    elif B[bi] >= C[ci]:
        sunuke(ai, bi, ci+1, ans)
    else:
        ans += 1
        sunuke(ai, bi, ci+1, ans)

ans = 0
sunuke(0,0,0, ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

def sunuke(ai, bi, ci, ans):

    if ai > N-1:
        print(ans)
    elif bi > N-1:
        sunuke(ai+1, 0, 0, ans)
    elif ci > N-1:
        sunuke(ai, bi+1, 0, ans)

    elif A[ai] >= B[bi]:
        sunuke(ai,bi+1,ci, ans)
    elif B[bi] >= C[ci]:
        sunuke(ai, bi, ci+1, ans)
    else:
        ans += 1
        sunuke(ai, bi, ci+1, ans)

ans = 0
sunuke(0,0,0, ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

def sunuke(ai, bi, ci):
    global ans

    if ai > N-1:
        print(ans)
    elif bi > N-1:
        sunuke(ai+1, 0, 0)
    elif ci > N-1:
        sunuke(ai, bi+1, 0)

    elif A[ai] >= B[bi]:
        sunuke(ai,bi+1,ci)
    elif B[bi] >= C[ci]:
        sunuke(ai, bi, ci+1)
    else:
        ans += 1
        sunuke(ai, bi, ci+1)

ans = 0
sunuke(0,0,0)