Problem p03557 (python)

Fixed submission:
import sys
import bisect

readline = sys.stdin.readline

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    A.sort()
    C.sort()

    ans = 0
    for b in B:
        ansA = bisect.bisect_left(A, b)
        ansC = N - bisect.bisect_right(C, b)
        ans += ansA * ansC

    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
import math
import collections

readline = sys.stdin.readline

def myindex(t, x, default=-1):
    if x in t:
        return t.index(x)
    else:
        return default


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    lenB = len(B)
    log2lenB = int(math.log2(lenB))

    A.sort()
    C.sort()

    countAlist = list(zip(*list(collections.Counter(A).items())))
    countClist = list(zip(*list(collections.Counter(C).items())))

    #print(countClist)

    sumAlist = [0] * (max(A)+1)
    sumClist = [0] * (max(C)+1)

    for i in range(max(A)+1):
        index = myindex(countAlist[0], i)
        sumAlist[i] = sumAlist[i-1] + (index >= 0) * countAlist[1][index]

    for i in range(max(C)+1):
        j = max(C) - i + 1
        index = myindex(countClist[0], j)
        sumClist[i] = sumClist[i-1] + (index >= 0) * countClist[1][index]

    ans = 0

    for i in range(lenB):
        target = B[i]
        upper = lenB - 1
        lower = 0
        middle = (upper + lower) // 2

        for _ in range(log2lenB+1):
            if target > max(A):
                lower = len(A) - 1
                break
            if target == A[middle]:
                lower = middle - 1
                break
            elif target < A[middle]:
                upper = middle
            else:
                lower = middle
            middle = (upper + lower) // 2 + 1
        
        ansA = sumAlist[A[lower]]
        #print('A:{} B:{} C:{}'.format(A, B, C))
        #print('A:{} B:{}, ansA:{}'.format(A[lower], target, ansA))

        upper = lenB - 1
        lower = 0
        middle = (upper + lower) // 2

        for _ in range(log2lenB+1):
            if target == C[middle]:
                upper = middle + 1
                break
            elif target < C[middle]:
                upper = middle
            else:
                lower = middle
            middle = (upper + lower) // 2

        ansC = sumClist[-C[upper]]
        #print('B:{} C:{}, ansC:{}'.format(target, C[upper], ansC))
        ans += ansA * ansC


    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
import math
import collections

readline = sys.stdin.readline

def myindex(t, x, default=-1):
    if x in t:
        return t.index(x)
    else:
        return default


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    lenB = len(B)
    log2lenB = int(math.log2(lenB))

    A.sort()
    C.sort()

    countAlist = list(zip(*list(collections.Counter(A).items())))
    countClist = list(zip(*list(collections.Counter(C).items())))

    #print(countClist)

    sumAlist = [0] * (max(A)+1)
    sumClist = [0] * (max(C)+1)

    for i in range(max(A)+1):
        index = myindex(countAlist[0], i)
        sumAlist[i] = sumAlist[i-1] + (index >= 0) * countAlist[1][index]

    for i in range(max(C)+1):
        j = max(C) - i + 1
        index = myindex(countClist[0], j)
        sumClist[i] = sumClist[i-1] + (index >= 0) * countClist[1][index]

    ans = 0

    for i in range(lenB):
        target = B[i]
        upper = lenB - 1
        lower = 0
        middle = (upper + lower) // 2

        for _ in range(log2lenB+1):
            if target > max(A):
                lower = len(A) - 1
                break
            if target == A[middle]:
                lower = middle - 1
                break
            elif target < A[middle]:
                upper = middle
            else:
                lower = middle
            middle = (upper + lower) // 2 + 1
        
        ansA = sumAlist[A[lower]]
        #print('A:{} B:{} C:{}'.format(A, B, C))
        #print('A:{} B:{}, ansA:{}'.format(A[lower], target, ansA))

        upper = lenB - 1
        lower = 0
        middle = (upper + lower) // 2

        for _ in range(log2lenB+1):
            if target == C[middle]:
                upper = middle + 1
                break
            elif target < C[middle]:
                upper = middle
            else:
                lower = middle
            middle = (upper + lower) // 2

        ansC = sumClist[-C[upper]]
        #print('B:{} C:{}, ansC:{}'.format(target, C[upper], ansC))
        ans += ansA * ansC


    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
import math
import collections

readline = sys.stdin.readline

def myindex(t, x, default=-1):
    if x in t:
        return t.index(x)
    else:
        return default


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    lenB = len(B)
    log2lenB = int(math.log2(lenB))

    A.sort()
    C.sort()

    countAlist = list(zip(*list(collections.Counter(A).items())))
    countClist = list(zip(*list(collections.Counter(C).items())))

    #print(countClist)

    sumAlist = [0] * (max(A)+1)
    sumClist = [0] * (max(C)+1)

    for i in range(max(A)+1):
        index = myindex(countAlist[0], i)
        sumAlist[i] = sumAlist[i-1] + (index >= 0) * countAlist[1][index]

    for i in range(max(C)+1):
        j = max(C) - i + 1
        index = myindex(countClist[0], j)
        sumClist[i] = sumClist[i-1] + (index >= 0) * countClist[1][index]

    ans = 0

    for i in range(lenB):
        target = B[i]
        upper = lenB - 1
        lower = 0
        middle = (upper + lower) // 2

        for _ in range(log2lenB+1):
            if target > max(A):
                lower = len(A) - 1
                break
            if target == A[middle]:
                lower = middle - 1
                break
            elif target < A[middle]:
                upper = middle
            else:
                lower = middle
            middle = (upper + lower) // 2 + 1
        
        ansA = sumAlist[A[lower]]
        print('A:{} B:{} C:{}'.format(A, B, C))
        print('A:{} B:{}, ansA:{}'.format(A[lower], target, ansA))

        upper = lenB - 1
        lower = 0
        middle = (upper + lower) // 2

        for _ in range(log2lenB+1):
            if target == C[middle]:
                upper = middle + 1
                break
            elif target < C[middle]:
                upper = middle
            else:
                lower = middle
            middle = (upper + lower) // 2

        ansC = sumClist[-C[upper]]
        print('B:{} C:{}, ansC:{}'.format(target, C[upper], ansC))
        ans += ansA * ansC


    print(ans)


if __name__ == "__main__":
    main()