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:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
d=[]
a.sort()
b.sort()
c.sort()
def binary_search(list,item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return guess+1
        if guess > item:
            if high == low:
                return high
            high = mid
        else:
            if high == low:
                return high + 1
            low = mid+1

def binary_search2(list,item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            if guess!=n-1:
                return d[guess+1]
            else:
                return 0
        if guess > item:
            if high == low:
                return d[high]
            high = mid
        else:
            if high == low:
                if high!=n-1:
                    return d[high+1]
                else:
                    return 0
            low = mid+1

for i in range(n):
    print(binary_search(c,b[i]))
    d.append(n-binary_search(c,b[i]))
print(d)
d.reverse()
import numpy
d=numpy.cumsum(d)
d=list(d)
d.reverse()
print(d)
ans=0

for i in range(n):
    ans+=binary_search2(b,a[i])

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_right
read=sys.stdin.read
readline=sys.stdin.readline

def main():
    n=int(readline())
    a,b,c=(list(map(int,lst.split())) for lst in read().splitlines())
    a.sort()
    b.sort()
    c=[-x for x in c]
    c.sort()
    print(sum(bisect_right(x,a)*bisect_right(-x,c) for x in b))

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def bs_left(lists, item):
    low, high = 0, len(lists)
    
    while (high >low ) :
        mid = (low + high)//2
        if lists[mid]  < item:
            low = mid +1
            
        else:
            high = mid
            
    return low

def bs_right(lists, item):
    low, high = 0, len(lists)
    
    while (high >low ):
        mid = (low + high)//2
        if lists[mid] > item:
            high = mid 
            
        else:
            low = mid+1
            
    return len(lists) - low
  

Code
n = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
​
count = 0
A.sort(), B.sort(), C.sort()
for b in B:
    count += (bs_left(A, b) * bs_right(C, b))
    
print(count)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

an.sort()
bn.sort()
cn.sort()

cnt = 0

for b in bn:
    a = bisect_left(an,b)
    c = bisect_right(cn,b)
    cnt += a * (n-c)
print(cnt)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

def less_than(array, x):
    # arrayの中のx未満のものの個数
    # arrayの中のx未満のもののうちの最大値
    index = bisect_left(array, x)
    if index == 0:
        less_than_int = -float('inf')
    else:
        less_than_int = array[index - 1]
    return [index, less_than_int]

N = getN()
up = getList()
up.sort()
mid = getList()
mid.sort()
low = getList()
low.sort()

# 中段のパーツに載せられる上段のパーツの数
mid_imos = [0] * 6
for i in range(N):
    mid_imos[i] = less_than(up, mid[i])[0]

for i in range(N - 1):
    mid_imos[i + 1] += mid_imos[i]

low_imos = [0] * 6
for i in range(N):
    ind = less_than(mid, low[i])[0]
    if ind > 0:
        low_imos[i] = mid_imos[ind - 1]
print(sum(low_imos))

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect
from itertools import accumulate


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = sorted(map(int, input().split()))
    b = sorted(map(int, input().split()))
    c = sorted(map(int, input().split()))
    # 各中部パーツを乗せられる下部パーツの個数
    # b_c_cnt = [len(c[bisect(c, b[i]) :]) for i in range(n)]
    b_c_cnt = [0] * n
    past = 0
    for i in range(n):
        pos = bisect(c, b[i], lo=past)
        past = pos
        b_c_cnt[i] = n - pos

    # b_c_cntに後ろから累積和をとる
    acc = list(accumulate(b_c_cnt[::-1]))[::-1]
    ans = 0
    past = 0
    for i in range(n):
        pos = bisect(b, a[i], lo=past)
        ans += acc[pos]
        past = pos
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect
from itertools import accumulate


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = sorted(map(int, input().split()))
    b = sorted(map(int, input().split()))
    c = sorted(map(int, input().split()))
    # 各中部パーツを乗せられる下部パーツの個数
    b_c_cnt = [len(c[bisect(c, b[i]) :]) for i in range(n)]
    # b_c_cntに後ろから累積和をとる
    acc = list(accumulate(b_c_cnt[::-1]))[::-1]
    ans = 0
    for i in range(n):
        ans += acc[bisect(b, a[i])]
    print(ans)


if __name__ == "__main__":
    main()

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()))
ans = 0

#リストをソート
A,B,C = sorted(A),sorted(B),sorted(C)

for i in range(N):
  middle = 0
  bottom = 0
  bool1 = True
  while True:
    if middle == N:
      break
    if B[middle] > A[i]:
      while True:
        if C[bottom] > B[middle]:
          ans += len(C[bottom:])
          break
        bottom += 1
    middle += 1
print(ans)

Submission status: Runtime Error

Solution code:
def binary(list_a,item):
  low=0
  high=len(list_a)-1
  while (high-low)>1:
    mid=int((low+high)/2)
    tmp=list_a[mid]
    if tmp>item:
      high=mid
    elif tmp<item:
      low=mid
    elif tmp==item:
      eq=[i for i, x in enumerate(list_a) if x == tmp]
      high=eq[-1]
      low=eq[0]
      return low-1,high+1
  return low,high

def 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())))
  ans=0
  for b in B:
    a_low,a_high=binary(A,b)
    c_low,c_high=binary(C,b)
    
    if b>A[a_high]:
      a_low=N-1
    elif b<A[a_low]:
      a_low=0
      
    if b<C[c_low]:
      c_high=0
    elif b>C[c_high]:
      c_high=N
    
    ans+=(a_low+1)*(N-c_high)
  print(ans)
  
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
def binary(list_a,item):
  low=0
  high=len(list_a)-1
  while (high-low)>1:
    mid=int((low+high)/2)
    tmp=list_a[mid]
    if tmp>item:
      high=mid
    elif tmp<item:
      low=mid
    elif tmp==item:
      eq=[i for i, x in enumerate(list_a) if x == tmp]
      high=eq[-1]
      low=eq[0]
      return low-1,high+1
  return low,high


def 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())))
  print(A)
  print(B)
  print(C)
  ans=0
  for b in B:
    a_low,a_high=binary(A,b)
    c_low,c_high=binary(C,b)
    
    if b>A[a_high]:
      a_low=N-1
    elif b<A[a_low]:
      a_low=0
      
    if b<C[c_low]:
      c_high=0
    elif b>C[c_high]:
      c_high=N
    
    print(a_low+1,N-c_high)
    ans+=(a_low+1)*(N-c_high)
  print(ans)
  
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
def binary_search(list_a,item):
  low=0
  high=len(list_a)-1
  while low<=high:
    mid=int((low+high)/2)
    guss=list_a[mid]
    if guss>item:
      high=mid-1
    elif guss<item:
      low=mid+1
    elif guss==item:
      return mid
  return mid

def 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())))
  ans=0    
  for b in B:
    p=binary_search(A,b)
    if A[p]>b:
      tmp_p=p
    elif A[p]<b:
      tmp_p=p+1
    elif A[p]==b:
      while A[p]==A[p-1]:
        p-=1
      tmp_p=p
    q=binary_search(C,b)
    if C[q]>b:
      tmp_q=N-q
    elif C[q]<b:
      tmp_q=N-q-1
    elif C[q]==b:
      while C[q]==C[q+1]:
        q+=1
      tmp_q=N-q-1
    ans+=tmp_p*tmp_q
  print(ans)
  
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys


def main():
        n = sys.stdin.readline()

        astr = sys.stdin.readline()
        bstr = sys.stdin.readline()
        cstr = sys.stdin.readline()

        a = list(map(int, astr.strip().split(' ')))
        b = list(map(int, bstr.strip().split(' ')))
        c = list(map(int, cstr.strip().split(' ')))

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

        cnt = 0

        bc = []
        sum = 0
        for bi in reversed(b):
                ct = c[binary(bi, c):]
                sum += len(ct)
                bc.append(sum)
        bc.reverse()

        cnt = 0
        for ai in a:
                bi = binary(ai, b)
                cnt += bc[bi]

        print(cnt)


def binary(x, li):
    upper = len(li)
    lower = -1
    index = int((upper + lower) / 2)


    while upper - lower > 1:
        if (x < li[index]):
            upper = index
        else:
            lower = index
        index = int((upper + lower)/2)
    
    return upper


main()

Submission status: Runtime Error

Solution code:
from bisect from bisect_left

def search(li, x):
  None

n = int(input())

li = [[] for i in range(3)]
for i in range(3):
  li[i] = input.split()
print(li)

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()))
al=sorted(a)
bl=sorted(b)
cl=sorted(c)
 
abl=[0]*n
bcl=[0]*n
i=n-1
for j in range(n-1,-1,-1):
    while al[i]>=bl[j]:
        i-=1
        if i==-1:
            break
    if i==-1:
        abl[j]=0
    else:
        abl[j]=i+1
j=0
bcl=[0]*n
k=0
for j in range(n):
    while cl[k]<=bl[j]:
        k+=1
        if k==n:
            break
    if k==n:
        bcl[j]=0
    else:
        bcl[j]=(n-k)
ans=0
for s in range(n):
    ans+=abl[s]*bcl[s]
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()))

al=sorted(a)
bl=sorted(b)
cl=sorted(c)
print(al)
print(bl)
print(cl)
j=0
k=0
ans=0
saved_j=0
saved_k=0
for i in range(n):
    j=saved_j
    while al[i]>=bl[j]:
        j+=1
        saved_j=j
    #print("j",j)
    while j!=n:
        k=saved_k
        while bl[j]>=cl[k]:
            if k==n-1:
                break
            k+=1
        if j==saved_j:
            saved_k=k
        #print("k",k)
        ans+=n-k
        j+=1
        #print("暫定",ans)
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
abc=[list(map(int,input().split())) for i in range(3)]
sum=0
for _ in range(n):
  abc[1].append(abc[0][i])
  abc[1].sort()
  abc[2].sort()
  p=abc[1].index(abc[0][i])
  for k in range(p+1,n):
    abc[2].append(a[1][k])
    q=abc[2].index(abc[1][k])
    sum+=n-q-1
    abc[1].remove(abc[0][i])
    abc[2].remove(a[1][k])
print(sum)

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 b in B:
    a = bisect_left(A, b)
    c = bisect_right(C, b)
    ans += a*(N-c)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
al = list(map(int,input().split())).sort()
bl = list(map(int,input().split())).sort()
cl = list(map(int,input().split())).sort()

ans = 0
for b in bl:
    a_num = bisect.bisect_left(al,b)
    c_num = n - bisect.bisect_right(cl,b)
    ans += a_num*c_num

print(ans)

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
A = list(map(int, input().split()))
B= list(map(int, input().split()))
C= list(map(int, input().split()))
print(sum(bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b)) for b in B))

Submission status: Runtime Error

Solution code:
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()
b.sort()
c.sort()

bc = [0]*n
bc[n-1]=n-bisect.bisect_right(c, b[n-1])

for i in range(0,n-1):
  bc[n-2-i]=bc[n-1-i] + n-bisect.bisect_right(c, b[n-2-i])

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

Submission status: Runtime Error

Solution code:
import bisect
from collections import accumulate
n, *ABC = map(int, open(0).read().split())
A, B, C = ABC[:n], ABC[n:2*n], ABC[2*n:3*n]
A.sort()
B.sort()
C.sort()
D = [bisect.bisect_left(A, b) for b in B]
E = [bisect.bisect_left(B, c) for c in C]
F = list(accumulate(D))
s = 0
for e in E:
    if e != 0:
        s += F[e-1]
print(s)

Submission status: Runtime Error

Solution code:
N =int(input())
lisA =list(map(int,input().split()))
lisB = list(map(int,input().split()))
lisC = list(map(int,input().split()))

lisA.sort()
lisB.sort()
lisC.sort()
cnt = 0

for b in lisB:
    cnt+= bisect.bisect_left(lisA,b)*(N-bisect.bisect_right(lisC,b))

print(cnt)

Submission status: Runtime Error

Solution code:
N =int(input())
lisA =sorted(list(map(int,input().split())))
lisB = sorted(list(map(int,input().split())))
lisC = sorted(list(map(int,input().split())))



print(sum(bisect.bisect_left(lisA,b)*(N-bisect.bisect_right(lisC,b))for b in  lisB))

Submission status: Runtime Error

Solution code:
N =int(input())
lisA = list(map(int,input().split()))
lisB = list(map(int,input().split()))
lisC = list(map(int,input().split()))



print(sum(bisect.bisect_left(lisA,b)*(N-bisect.bisect_right(lisC,b))for b in  lisB))

Submission status: Runtime Error

Solution code:
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):
    b = B[i]
    a = bisect.bisect_left(A,b)
    c = bisect.bisect_right(C,b)
    ans+=(a*(len(C)-c))
print(ans)

Submission status: Runtime Error

Solution code:
# ABC077C

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())))

bC=[0 for i in range(N)]
for i in range(N):
    bC[i]=N-bisect.bisect(C,B[i])
    
bCS=[0]*N+1
for i in range(N):
    bCS[i+1] = bCS[i]+bC[i]
    
ans=0
for i in range(N):
    x=bisect.bisect(B,A[i])
    ans+=bCS[N]-bCS[x]
        
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
Lists = []
ans = 0
for _ in range(3):
    s = [int(e) for e in input().split()]
    s.sort()
print(Lists)
def a(right,left,i,j):
    global ans
    while(right >= left):
        mid =int(left + (right-left) / 2)
        if(i>=Lists[j][mid]):
            left = mid + 1
        else:
            right = mid - 1
    if(j == 2 and left <= N-1):
        ans += N-left
    elif(left <= N-1):
        for k in range(left,N):
            a(N-1,0,Lists[j][k],j+1)
for i in Lists[0]:
    a(N-1,0,i,1)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
Lists = []
ans = 0
for _ in range(3):
    s = [int(e) for e in input().split()]
    s.sort()
print(Lists)
def binary(right,left,i,j):
    global ans
    while(right >= left):
        mid =int(left + (right-left) / 2)
        if(i>=Lists[j][mid]):
            left = mid + 1
        else:
            right = mid - 1
    if(j == 2 and left <= N-1):
        ans += N-left
    elif(left <= N-1):
        for k in range(left,N):
            binary(N-1,0,Lists[j][k],j+1)
for i in Lists[0]:
    binary(N-1,0,i,1)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

import bisect

ans = 0
for b in range(B):
  k = bisect.bisect_left(A, b)
  l = bisect.bisect_right(C, b)
  ans += k * (N -l)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
A = sorted(tuple(map(int, input().split())))
B = tuple(map(int, input().split()))
C = sorted(tuple(map(int, input().split())))

count = 0
for b in B:
    # Aの候補
    la = -1
    ra = n
    while (ra - la) > 1:
        mid = (la+ra)//2
        if A[mid] > b:
            ra = mid
        else:
            la = mid
    if A[la] != b:
        la += 1

    # Cの候補
    lc = -1
    rc = n
    while (rc - lc) > 1:
        mid = (lc+rc)//2
        if C[mid] < b:
            lc = mid
        else:
            rc = mid
    if C[rc] == b:
        rc += 1
    
    count += la*(n-rc)

print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
A = sorted(tuple(map(int, input().split())))
B = tuple(map(int, input().split()))
C = sorted(tuple(map(int, input().split())))

count = 0
for b in B:
    # Aの候補
    la = -1
    ra = n
    while (ra - la) > 1:
        mid = (la+ra)//2
        if A[mid] > b:
            ra = mid
        else:
            la = mid
    if A[la] != b:
        la += 1

    # Cの候補
    lc = -1
    rc = n
    while (rc - lc) > 1:
        mid = (lc+rc)//2
        if C[mid] < b:
            lc = mid
        else:
            rc = mid
    if C[rc] == b:
        rc += 1
        
        count += la*(n-rc)
    
    print(count)

Submission status: Runtime Error

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

def binary_search(xs,target,maxlen,low,high,reverse=True):
    middle = 0
    while(low <= high):
        middle = (low + high) // 2
        can = xs[middle]
        if can == target:
            if reverse == False:
                return middle
            else:
                return middle + 1
        if can > target:
            high = middle - 1
        elif can < target:
            low = middle + 1

    middle = (low + high) // 2 +1
    return middle

def snuke_festival(a,b,c):
    count = 0
    a_sorted = sorted(a)
    b_sorted = sorted(b)
    c_sorted = sorted(c)
    maxlen=len(b)
    high = maxlen - 1
    low = 0
    mid_a = low
    mid_b = high

    for target in b_sorted:
        mid_a = binary_search(a_sorted,target,maxlen,mid_a,high,False)
        mid_b = binary_search(c_sorted,target,maxlen,low,mid_b,True)
        count += mid_a * (maxlen - mid_b)
    return count

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    c = list(map(int,input().split()))

    print(snuke_festival(a,b,c))

Submission status: Runtime Error

Solution code:
N = int(input())

A_list = list( map(int, input().split() ) )
B_list = list( map(int, input().split() ) )
C_list = list( map(int, input().split() ) )
# print(d,n,m)
# print(A_list)
# print(B_list)
# print(C_list)

A_sort = sorted(A_list)
C_sort = sorted(C_list)
# print(A_sort)
# print(C_sort)

# kよりも小さい値の位置を探す
def search_lower_num(a_list, k):
    low = 0
    high = len(a_list) - 1
    mid = (low + high)//2

    if a_list[high] < k:
        return a_list[:high+1]
    elif a_list[low] > k:
        return None

    while low <= high:
        mid = (low + high)//2

        if mid-1 >= 0:
            if a_list[mid-1] < k \
                and a_list[mid] >= k:
                return a_list[:mid]

        # 2分探索する。
        if a_list[mid] <= k:
            low = mid + 1
        elif a_list[mid] > k:
            high = mid - 1

    return None

# kよりも大きい値の位置を探す
def search_upper_num(a_list, k):
    low = 0
    high = len(a_list) - 1
    mid = (low + high)//2

    if a_list[low] > k:
        return a_list[low:]
    elif a_list[high] < k:
        return None

    while low <= high:
        mid = (low + high)//2

        if mid+1 < len(a_list):
            if a_list[mid] <= k \
                and a_list[mid+1] > k:
                return a_list[mid+1:]

        # 2分探索する。
        if a_list[mid] < k:
            low = mid + 1
        elif a_list[mid] >= k:
            high = mid - 1

    return None

sum_conbi = 0
for B in B_list:
    a_result = search_lower_num(A_sort, B)
    c_result = search_upper_num(C_sort, B)

    # print(a_result)
    # print(c_result)

    sum_conbi += len(a_result) * len(c_result)

print(sum_conbi)

Submission status: Runtime Error

Solution code:
N = int(input())

A_list = list( map(int, input().split() ) )
B_list = list( map(int, input().split() ) )
C_list = list( map(int, input().split() ) )
# print(d,n,m)
# print(A_list)
# print(B_list)
# print(C_list)

A_sort = sorted(A_list)
C_sort = sorted(C_list)
# print(A_sort)
# print(C_sort)

# kよりも小さい値の位置を探す
def search_lower_num(a_list, k):
    low = 0
    high = len(a_list) - 1
    mid = (low + high)//2

    while low <= high:
        mid = (low + high)//2

        if mid-1 >= 0:
            if a_list[mid-1] < k \
                and a_list[mid] >= k:
                return a_list[:mid]

        # 2分探索する。
        if a_list[mid] < k:
            low = mid + 1
        elif a_list[mid] > k:
            high = mid - 1
        else:
            return None

    if a_list[mid] < k:
        return a_list[:mid+1]

    return None

# kよりも大きい値の位置を探す
def search_upper_num(a_list, k):
    low = 0
    high = len(a_list) - 1
    mid = (low + high)//2

    while low <= high:
        mid = (low + high)//2

        if mid+1 < len(a_list):
            if a_list[mid] <= k \
                and a_list[mid+1] > k:
                return a_list[mid+1:]

        # 2分探索する。
        if a_list[mid] < k:
            low = mid + 1
        elif a_list[mid] > k:
            high = mid - 1
        else:
            return a_list[mid:]

    if a_list[mid] > k:
        return a_list[mid:]

    return None




sum_conbi = 0
for B in B_list:
    a_result = search_lower_num(A_sort, B)
    c_result = search_upper_num(C_sort, B)

    # print(a_result)
    # print(c_result)

    sum_conbi += len(a_result) * len(c_result)

print(sum_conbi)

Submission status: Runtime Error

Solution code:
import bisect

def quicksort(x):
    if x==[]: return []

    smallerSorted = quicksort([a for a in x[1:] if a <= x[0]])
    biggerSorted = quicksort([a for a in x[1:] if a > x[0]])

    return(smallerSorted+[x[0]]+biggerSorted)


ans = 0
N = int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A = quicksort(A)
B = quicksort(B)
C = quicksort(C)

length = len(A)
#A<B<Cの組み合わせの数が答え
for i in range(length):
    #Aを1つ決めた時、BがA以下の値
    A_miman = bisect.bisect_right(B,A[i])
    for j in range(A_miman,N):
        #Bを1つ決めた時、CがBより大きい値の数をansに足す
        ans += N - bisect.bisect_right(C, B[j])
        


print(ans)

Submission status: Runtime Error

Solution code:
# 汎用的な二分探索のテンプレ
def binary_search1(key, a):
    left = -1 # index = 0 が条件を満たすこともあるので初期値は−１
    right = len(a) # index = len(a) -1 が条件満たさないこともある

    # どんな二分探索でもここの書き方を変えずにできる
    while right - left > 1 :
        mid = left + ((right - left + 1) // 2)
        if a[mid] >= key: 
            right = mid
        else:
            left = mid
    return right

def binary_search2(key : int, a : List[int]):
    left = -1 # index = 0 が条件を満たすこともあるので初期値は−１
    right = len(a) # index = len(a) -1 が条件満たさないこともある

    # どんな二分探索でもここの書き方を変えずにできる
    while right - left > 1 :
        mid = left + ((right - left + 1) // 2)
        if a[mid] > key:
            right = mid
        else:
            left = mid
    return right

import sys

def main():

    _ = int(input())
    a_l = sorted(list(map(int, sys.stdin.readline().strip().split())))
    b_l = sorted(list(map(int, sys.stdin.readline().strip().split())))
    c_l = sorted(list(map(int, sys.stdin.readline().strip().split())))
    cnt = 0
    for b in b_l:
        a_under_b_idx = binary_search1(b, a_l)
        c_upper_b_idx = binary_search2(b, c_l)
        cnt += len(a_l[:a_under_b_idx])*len(c_l[c_upper_b_idx:])
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# index が条件をみたかどうか
def isLess(index, key, a):
	if a[index] >= key:
		return True
	else: 
		return False
      
def isUpper(index, key, a):
	if a[index] > key:
		return True
	else: 
		return False
      
def binary_search(key, a, upper=True):
    left = -1 # index = 0 が条件を満たすこともあるので初期値は−１
    right= len(a) # index = len(a) -1 が条件満たさないこともある
 
    # どんな二分探索でもここの書き方を変えずにできる
    while right - left > 1 :
        mid = left + ((right - left + 1) // 2)
        if upper:
            if isUpper(mid, key, a): # isOKの名前でこの関数内の条件判定変えれば色々できそう
                right = mid
            else:
                left = mid
        else:
            if isLess(mid, key, a): # isOKの名前でこの関数内の条件判定変えれば色々できそう
                right = mid
            else:
                left = mid
    return right

import sys

def main():
    n = int(input())
    a_l = sorted(list(map(int, sys.stdin.readline().strip().split()))
    b_l = sorted(list(map(int, sys.stdin.readline().strip().split()))
    c_l = sorted(list(map(int, sys.stdin.readline().strip().split()))
    cnt = 0
    for b in b_l:
        a_under_b_idx = binary_search(b, a_l, upper=False)
        c_upper_b_idx = binary_search(b, c_l)
        cnt += len(a_l[:a_under_b_idx])*len(c_l[c_upper_b_idx:])
    print(cnt)
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
 
# index が条件をみたかどうか
def isLess(index, key, a):
	if a[index] >= key:
		return True
    else: 
		return False
      
def isUpper(index, key, a):
    if a[index] > key:
		return True
    else: 
		return False
      
def binary_search(key, a, upper=True):
    left = -1 # index = 0 が条件を満たすこともあるので初期値は−１
    right= len(a) # index = len(a) -1 が条件満たさないこともある
 
    # どんな二分探索でもここの書き方を変えずにできる
    while right - left > 1 :
        mid = left + ((right - left + 1) // 2)
        if upper:
            if isUpper(mid, key, a): # isOKの名前でこの関数内の条件判定変えれば色々できそう
                right = mid
            else:
                left = mid
        else:
            if isLess(mid, key, a): # isOKの名前でこの関数内の条件判定変えれば色々できそう
                right = mid
            else:
                left = mid
    return right
  
def main():
    n = int(input())
    a_l = sorted(list(map(int, input().split())))
    b_l = sorted(list(map(int, input().split())))
    c_l = sorted(list(map(int, input().split())))
    cnt = 0
    for b in b_l:
        a_under_b_idx = binary_search(b, a_l, upper=False)
        c_upper_b_idx = binary_search(b, c_l)
        cnt += len(a_l[:a_under_b_idx])*len(c_l[c_upper_b_idx:])
    print(cnt)
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
 
# index が条件をみたかどうか
def isLess(index, key, a):
	if a[index] >= key:
        return True
    else: 
		return False
      
def isUpper(index, key, a):
    if a[index] > key:
		return True
    else: 
		return False
      
def binary_search(key, a, upper=True):
    left = -1 # index = 0 が条件を満たすこともあるので初期値は−１
    right= len(a) # index = len(a) -1 が条件満たさないこともある
 
    # どんな二分探索でもここの書き方を変えずにできる
    while right - left > 1 :
        mid = left + ((right - left + 1) // 2)
        if upper:
            if isUpper(mid, key, a): # isOKの名前でこの関数内の条件判定変えれば色々できそう
                right = mid
            else:
                left = mid
        else:
            if isLess(mid, key, a): # isOKの名前でこの関数内の条件判定変えれば色々できそう
                right = mid
            else:
                left = mid
    return right
  
def main():
    n = int(input())
    a_l = sorted(list(map(int, input().split())))
    b_l = sorted(list(map(int, input().split())))
    c_l = sorted(list(map(int, input().split())))
    cnt = 0
    for b in b_l:
        a_under_b_idx : int = binary_search(b, a_l, upper=False)
        c_upper_b_idx : int = binary_search(b, c_l)
        cnt += len(a_l[:a_under_b_idx])*len(c_l[c_upper_b_idx:])
    print(cnt)
    
    
if __name__ == '__main__':
    main()