Problem p03557 (python)

Fixed submission:
#!/usr/bin/env python3

import bisect

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_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
# if N == 1:
#     if A[0] < B[0] < C[0]:
#         count += 1
# else:
#     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}")
#         if index_A != None and index_C != None:
#             count += (index_A + 1) * (N - index_C)

# print(count)

count = 0
for bot in B:
    i_A = bisect.bisect_left(A, bot)
    i_C = bisect.bisect_right(C, bot)
    count += i_A * (N - i_C)
print(count)

Buggy submission (verdict: Runtime Error):
#!/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)


def is_ok(array, index, value):
    if array[index] >= value:
        return True
    return False


def bs_general(array, value, is_ok):
    left = -1
    right = len(array)
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if is_ok(array, mid, value):
            right = mid
        else:
            left = mid
    return right


res = 0
for b in B:
    index_a = bs_general(A, b, is_ok)
    index_c = bs_general(C, b, is_ok)
    if C[index_c] == b:
        res += index_a * (N - index_c - 1)
    else:
        res += index_a * (N - index_c)

print(res)

Buggy submission (verdict: Runtime Error):
#!/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)

Buggy submission (verdict: Runtime Error):
#!/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)

Buggy submission (verdict: Runtime Error):
#!/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)

Buggy submission (verdict: Runtime Error):
#!/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)

Buggy submission (verdict: Runtime Error):
#!/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)

Buggy submission (verdict: Runtime Error):
#!/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)