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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
from bisect import bisect_left, bisect_right

def solve():
    N = II()
    A = sorted(LI())
    B = LI()
    C = sorted(LI())

    # print(A)
    # print(B)
    # print(C)
    ans = 0
    for b in B:
        # a < b
        i = bisect_left(A, b)

        # b < c
        j = N - bisect_right(C, b)
        # print(b, i, j)
        ans += i * j
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import bisect

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
B = LI()
C = LI()

A.sort()
B.sort()
C.sort()
ans = 0

for b in B:
    ok_a = bisect.bisect_left(A,b)
    ok_c = bisect.bisect_right(C,b)
    ans += ok_a*(N-ok_c)
print(ans)

Submission status: Accepted

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

ans = 0

for b in B:
    i = bisect.bisect_left(A, b)
    j = bisect.bisect(C, b)
    ans += i * (N - j)
print(ans)

Submission status: Accepted

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] * N
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] * N
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: Accepted

Solution code:
import bisect

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

ans = 0
for b in B:
  a_ind = bisect.bisect_left(A, b)
  c_ind = bisect.bisect_right(C, b)
  ans += a_ind*(n-c_ind)
  
print(ans)

Submission status: Accepted

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] + [0]
    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: Accepted

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

cnt = []
pos_c = 0
for pos_b in range(n):
    while pos_c < n and c[pos_c] <= b[pos_b]:
        pos_c += 1
    cnt.append(n - pos_c)

sum_cnt = [0] * (n+1)
sum_cnt[n-1] = cnt[n-1]
for i in range(n-2, -1, -1):
    sum_cnt[i] = sum_cnt[i+1] + cnt[i]

res = 0
pos_b = 0
for pos_a in range(n):
    while pos_b < n and b[pos_b] <= a[pos_a]:
        pos_b += 1
    res += sum_cnt[pos_b]

print(res)

Submission status: Accepted

Solution code:
import bisect
(n,),aa,bb,cc = [sorted(list(map(int, s.split()))) for s in open(0)]

ans = 0
for b in bb:
    ans += (bisect.bisect_left(aa,b))*(n-bisect.bisect_right(cc,b))

print(ans)

Submission status: Accepted

Solution code:
import bisect

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

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

Submission status: Accepted

Solution code:
import bisect
n = int(input())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
list_C = list(map(int, input().split()))
list_A.sort()
list_B.sort()
list_C.sort()
ans = 0

for i in range(n):
    b = list_B[i]
    left = bisect.bisect_left(list_A, b)
    right = n - bisect.bisect_right(list_C, b)
    ans += left * right

print(ans)

Submission status: Accepted

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

sm=0

for i,y in enumerate(b):
    mn_x=-1
    mx_x=n
    while mx_x-mn_x>=2:
        mid=(mn_x+mx_x)//2
        if a[mid]<y:
            mn_x=mid
        else : mx_x=mid

    mn_z=-1
    mx_z=n
    while mx_z-mn_z>=2:
        mid=(mn_z+mx_z)//2
        if c[mid]>y:
            mx_z=mid
        else : mn_z=mid
    
    sm+=(mn_x+1)*(n-mx_z)

print(sm)

Submission status: Accepted

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()
sum = 0
for i in range(n):
    l = bisect.bisect_left(a,b[i])
    r = bisect.bisect_right(c,b[i])
    sum += l*(n-r)
    
print(sum)

Submission status: Accepted

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

for i in b:
  ans += bisect.bisect_left(a, i) * (n - bisect.bisect_right(c, i))

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
#print(A)
A.sort()
B.sort()
C.sort()
#print(A)
import bisect

ans=0
for i in range(N):
    cnt=bisect.bisect_left(A,B[i])*(N-bisect.bisect_right(C,B[i]))
    ans+=cnt
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
U=list(map(int,input().split()))
S.sort()
T.sort()
U.sort()
#print(S)
#print(T)
#print(U)


count=0
def is_ok(index,key):
    if key>S[index]:
        return True
    else:
        return False


def meguru_bisect(key):
    ng=N
    ok=-1
    
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid,key):
            ok = mid
        else:
            ng = mid
    return ok

def is_ok2(index,key):
    if key<U[index]:
        return True
    else:
        return False


def meguru_bisect2(key):
    ng=-1
    ok=N
    
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok2(mid,key):
            ok = mid
        else:
            ng = mid
    return ok
ans=0
for i in range(N):
    ans+=(N-meguru_bisect2(T[i]))*(meguru_bisect(T[i])+1)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
U=list(map(int,input().split()))
S.sort()
T.sort()
U.sort()
#print(S)
#print(T)
#print(U)


count=0
def is_ok(index,key):
    if key>S[index]:
        return True
    else:
        return False


def meguru_bisect(key):
    ng=N
    ok=-1
    
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid,key):
            ok = mid
        else:
            ng = mid
    return ok

def is_ok2(index,key):
    if key<U[index]:
        return True
    else:
        return False


def meguru_bisect2(key):
    ng=-1
    ok=N
    
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok2(mid,key):
            ok = mid
        else:
            ng = mid
    return ok
ans=0
for i in range(N):
    ans+=(N-meguru_bisect2(T[i]))*(meguru_bisect(T[i])+1)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



# ここから書き始める
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())))

ans = 0
for i in range(n):
    ng = -1
    ok = n
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if a[mid] < b[i]:
            ok = mid
        else:
            ng = mid
    
    ng2 = -1
    ok2 = n
    while abs(ok2 - ng2) > 1:
        mid2 = (ok2 + ng2) // 2
        if c[mid2] > b[i]:
            ok2 = mid2
        else:
            ng2 = mid2

    # print("ok =", ok)
    # print("ok2 =", ok2)
    ans += (n - ok) * (n - ok2)

print(ans)

Submission status: Accepted

Solution code:
import bisect

def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = list(map(int, input().split()))
    C = sorted(list(map(int, input().split())))
    # print(N, A, B, C)
    # print(A)
    # print(B)
    # print(C)
    ans = 0
    for b in B:
        indexa = bisect.bisect_left(A, b)
        indexc = bisect.bisect_right(C, b)
        ans += indexa * (N - indexc)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = list(sorted(list(map(int,input().split()))))
B = list(map(int,input().split()))
C = list(sorted(list(map(int,input().split()))))
ans = 0
for b in B:
    ans +=(bisect.bisect_right(A,b-1))*(N-bisect.bisect_left(C,b+1))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A,B,C=[list(sorted(map(int,input().split()))) for i in range(3)]

count=0

def bs_l(lis,x):
    low,high=0,len(lis)
    while low<high:
        mid=(low+high)//2
        if lis[mid]<x:
            low=mid+1
        else:
            high=mid
    return low        

def bs_r(lis,x):
    low,high=0,len(lis)
    while low<high:
        mid=(low+high)//2
        if lis[mid]>x:
            high=mid
        else:
            low=mid+1
    return low        

for i in B:
    count+=bs_l(A,i)*(N-bs_r(C,i))


print(count)

Submission status: Accepted

Solution code:
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())))
print(sum(bisect.bisect_left(a,i)*(n-bisect.bisect_right(c,i)) for i in b))

Submission status: Accepted

Solution code:
n=int(input())
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))
C=[0]+list(map(int,input().split()))

A.sort()
B.sort()
C.sort()

total = [0]*(n+1)
ans = [0]*(n+1)
for i in range(n+1):
    l1 = 0
    r1 = n+1
    while l1 != r1:
        mid1 = (l1 + r1)//2
        if B[i] > A[mid1]:
            l1 = mid1 + 1
            total[i]=max(total[i],mid1+total[i-1])
        else:
            r1 = mid1

for i in range(n+1):
    l2 = 0
    r2 = n+1
    while l2 != r2:
        mid2 = (l2 + r2)//2
        if C[i] > B[mid2]:
            l2 = mid2 + 1
            ans[i] = max(ans[i],total[mid2])
        else:
            r2 = mid2
print(sum(ans))

Submission status: Accepted

Solution code:
#%%

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

#%%

def isok_A(index, key, arr):
    if arr[index] >= key:
        return True
    else:
        return False
 
def Binary_search_A(key, arr):
    
    ng = -1
    ok = len(arr)
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isok_A(mid, key, arr) is True:
            ok = mid
        else:
            ng = mid
    
    return ng, ok

def isok_B(index, key, arr):
    if arr[index] > key:
        return True
    else:
        return False

def Binary_search_B(key, arr):
    
    ng = -1
    ok = len(arr)
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isok_B(mid, key, arr) is True:
            ok = mid
        else:
            ng = mid
    
    return ng, ok

cnt = 0
for i in B:
    ng_a, ok_b = Binary_search_A(i, A)
    ng_c, ok_c = Binary_search_B(i, C)
    cnt += (ng_a + 1) * (N - ok_c)
print(cnt)

Submission status: Accepted

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

A,B,C = sorted(A),sorted(B),sorted(C)

for b in B:
  a = bisect.bisect_left(A,b)
  c = bisect.bisect_right(C,b)
  ans += a*(N-c)
  
print(ans)

Submission status: Accepted

Solution code:
import bisect

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=bisect.bisect_left(A,b)
    c=N-bisect.bisect_right(C,b)
    ans+=a*c
  print(ans)
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=list(map(int,input().split()))
b.sort()
c=list(map(int,input().split()))
c.sort()
ans=0
import bisect
for bb in b:
  ao=bisect.bisect(a,bb-1)
  cnta=ao
  cs=bisect.bisect(c,bb)
  cntc=n-cs
  ans+=cnta*cntc
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=list(map(int,input().split()))
b.sort()
c=list(map(int,input().split()))
c.sort()
ans=0
import bisect
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: Accepted

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()))
a.sort()
b.sort()
c.sort()
len_c = len(c)
total = 0
for num in b:
    idx_a = bisect_left(a, num)
    idx_c = bisect_right(c, num)
    cnt = idx_a * (len_c - idx_c)
    total += cnt
print(total)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline


def main():
    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:
        n_a = bisect_left(A, b)
        n_c = N - bisect_right(C, b)
        ans += n_a * n_c

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:],i8)", cache=True)
def binary_search(a, key):
    """Meguru type binary search"""
    ng = -1
    ok = len(a)

    def is_ok(a, key, idx):
        if a[idx] > key:
            return True
        else:
            return False

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(a, key, mid):
            ok = mid
        else:
            ng = mid

    return ok


@nb.njit("i8(i8,i8[:],i8[:],i8[:])", cache=True)
def solve(N, A, B, C):
    A.sort()
    B.sort()
    C.sort()

    BC = np.zeros(shape=N + 1, dtype=np.int64)
    for i in range(N):
        BC[i] = N - binary_search(C, B[i])

    ans = 0
    for a in A:
        idx = binary_search(B, a)
        ans += np.sum(BC[idx:])

    return ans


def main():
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    B = np.array(input().split(), dtype=np.int64)
    C = np.array(input().split(), dtype=np.int64)

    ans = solve(N, A, B, C)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import numpy as np
import random
import bisect
# stdin = open("sample.txt")


MOD = 1000000007
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr


    
def main():
    n = int(stdin.readline().rstrip())
    a_kari = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    a = sorted(a_kari)
    b_kari = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    b = sorted(b_kari)
    c_kari = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    c = sorted(c_kari)
    board_ab = [0] * n
    board_bc = [0] * n
    ans = 0
    
    for i in range(n):
        ab = bisect.bisect_left(a, b[i])
        bc = n - bisect.bisect_right(c, b[i])
        ans += ab * bc
        # print(ab,bc)
    print(ans)
    
main()

Submission status: Accepted

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
from bisect import bisect_left,bisect_right
for b in B:
    ida = bisect_left(A,b)
    idc = bisect_right(C,b)
    ans += ida*(N-idc)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy,deepcopy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N = i()
C = l()
B = l()
A = l()
B.sort()
C.sort()
l = []
for i in range(N):
    l.append(bisect.bisect_left(C,B[i]))
ruiseki = [0]+list(itertools.accumulate(l))
ans = 0
for i in range(N):
    num = bisect.bisect_left(B,A[i])
    ans += ruiseki[num]
print(ans)

Submission status: Accepted

Solution code:
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())))
counter = 0
for i in range(len(B)):
    #Bより小さいAの探索
    Ind_A = bisect.bisect_left(A,B[i])
    if A[Ind_A-1] == B[i]:
        Ind_A -= 1
    
    #Bより大きいCの探索
    Ind_C = bisect.bisect_right(C,B[i])
    num_C = len(C)-Ind_C
    counter += round(Ind_A*num_C)
    #print('B[i] =' +str(B[i]),end='')
    #print(' Ind_A =' +str(Ind_A),end='')
    #print(' Ind_C =' +str(Ind_C),end = '')
    #print(' num_C =' +str(num_C),end = '')    
    #print(' 総数 ' + str(Ind_A*num_C))
print(counter)

Submission status: Accepted

Solution code:
import sys

import time


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
        timesum = 0
        for bi in reversed(b):
                sum += len(c) - binary(bi,c)
                bc.append(sum)
        bc.reverse()

        cnt = 0
        for ai in a:
                bi = binary(ai, b)
                if(bi < len(bc)):
                    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: Accepted

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

ans = 0
for x in b:
    ans += (bisect.bisect_left(a, x)) * (n - bisect.bisect_right(c, x))

print(ans)

Submission status: Accepted

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

for i in b:
    an = bisect.bisect_left(a, i)
    cn = bisect.bisect_right(c, i)
    ans += an*(n - cn)

print(ans)

Submission status: Accepted

Solution code:
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())))

count=0
for i in B :
    a=bisect.bisect_left(A,i)
    c=bisect.bisect_right(C,i)
    p=a*(N-c)
    count+=p

print(count)

Submission status: Accepted

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):
    if i==-1:
        abl[j]=0
        continue
    while al[i]>=bl[j]:
        i-=1
        if i==-1:
            break
    if i==-1:
        abl[j]=0
    else:
        abl[j]=i+1
k=0
for j in range(n):
    if k==n:
        bcl[j]=0
        continue
    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: Accepted

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):
    if i==-1:
        abl[j]=0
        continue
    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):
    if k==n:
        bcl[j]=0
        continue
    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: Accepted

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()
C.sort()
ans=0
for b in B:
    ok=-1
    ng=N
    while ng-ok > 1:
        mid = (ok+ng) // 2 # 平均(小数切り捨て)
        if A[mid]<b:
            ok = mid
        else:
            ng = mid
    A_num=ok+1

    ok=N
    ng=-1
    while ok-ng > 1:
        mid = (ok+ng) // 2 # 平均(小数切り捨て)
        if C[mid]>b:
            ok = mid
        else:
            ng = mid
    C_num=N-(ng+1)
    ans+=A_num*C_num
print(ans)