Problem:


Score : 500 points

Problem Statement

   #nck {
      width: 30px;
      height: auto;
   }

There are N computers and N sockets in a one-dimensional world.
The coordinate of the i-th computer is a_i, and the coordinate of the i-th socket is b_i.
It is guaranteed that these 2N coordinates are pairwise distinct.

Snuke wants to connect each computer to a socket using a cable.
Each socket can be connected to only one computer.

In how many ways can he minimize the total length of the cables?
Compute the answer modulo 10^9+7.

Constraints

1 ≤ N ≤ 10^5

0 ≤ a_i, b_i ≤ 10^9

The coordinates are integers.

The coordinates are pairwise distinct.

Input

The input is given from Standard Input in the following format:

N
a_1
:
a_N
b_1
:
b_N

Output

Print the number of ways to minimize the total length of the cables, modulo 10^9+7.

Sample Input 1

2
0
10
20
30

Sample Output 1

2

There are two optimal connections: 0-20, 10-30 and 0-30, 10-20.
In both connections the total length of the cables is 40.

Sample Input 2

3
3
10
8
7
12
5

Sample Output 2

1



Sample input:
2
0
10
20
30


Sample output:
2

Submission status: Accepted

Solution code:
N = int(input())
Q = sorted([[int(input()), i//N] for i in range(2*N)])

mod = 10**9 + 7
ans = 1
S = [0, 0]

for i in Q:
    if S[1-i[1]] == 0:
        S[i[1]] += 1
    else:
        ans = (ans*S[1-i[1]]) % mod
        S[1-i[1]] -= 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
AB = []
for _ in range(N):
  AB.append([int(input()),True])
for _ in range(N):
  AB.append([int(input()),False])
AB.sort(key = lambda x:x[0])

ans = 1
c = 0
for _,f in AB:
  if f:
    c += 1
  else:
    if c>0:
      ans *= c
      c -= 1
      ans %= 10**9+7
    else:
      c -= 1
      ans *= -1*c
      ans %= 10**9+7
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def solve(n, a, b):
    v = []
    for i in range(n):
        v.append((a[i], 1))
        v.append((b[i], -1))
    v = sorted(v, key=lambda _:_[0])
    ans, cnt = 1, 0
    for _, t in v:
        if (cnt != 0) and (cnt * t < 0):
            ans = (ans * abs(cnt)) % MOD
        cnt += t
    return ans

n = int(input())
a = [int(input()) for i in range(n)]
b = [int(input()) for i in range(n)]
print(solve(n, a, b))

Submission status: Accepted

Solution code:
from bisect import *
N=int(input())
A=[int(input()) for _ in range(N)]
B=[int(input()) for _ in range(N)]
A=sorted(A)
B=sorted(B)
ans=1
mod=10**9+7
for a,b in zip(A,B):
  if a>b:
    a,b=b,a
  ans*=(bisect_right(A,b)-bisect_left(A,a))
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# cf16-exhibition-final-openA - 1D Matching
def calc(x, y, total):
    MOD = 10 ** 9 + 7
    if y:
        total = (total * y) % MOD
        y -= 1
    else:
        x += 1
    return x, y, total


def main():
    # sort A, B and the lines between A, B shouldn't cross
    # cross <-> not min distance
    N, *AB = map(int, open(0))
    C = sorted([(i, 1) for i in AB[:N]] + [(i, 0) for i in AB[N:]])
    ans, a, b = 1, 0, 0
    for i, t in C:
        if t:  # laptop
            a, b, ans = calc(a, b, ans)
        else:  # power sources
            b, a, ans = calc(b, a, ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# cf16-exhibition-final-openA - 1D Matching
def calc(x, y, total):
    if y:
        total = (total * y) % MOD
        y -= 1
    else:
        x += 1
    return x, y, total


def main():
    global MOD
    # sort A, B and the lines between A, B shouldn't cross
    # cross <-> not min distance
    N, *AB = map(int, open(0))
    C = sorted([(i, 1) for i in AB[:N]] + [(i, 0) for i in AB[N:]])
    MOD = 10 ** 9 + 7
    ans, a, b = 1, 0, 0
    for i, t in C:
        if t:  # laptop
            a, b, ans = calc(a, b, ans)
        else:  # power sources
            b, a, ans = calc(b, a, ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,*E=map(int,open(0))
a,c=1,0
for _,d in sorted((e,2*(i<N)-1)for i,e in enumerate(E)):
	if c*d<0:a=abs(a*c)%(10**9+7)
	c+=d
print(a)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0))
d={}
for i in a[:n]:d[i]=0
for i in a[n:]:d[i]=1
a,c=1,0
for i in sorted(d):
  if((c>0)!=d[i])*c:a=a*abs(c)%(10**9+7)
  c+=d[i]or-1
print(a)

Submission status: Accepted

Solution code:
mod = 10**9+7

n = int(input())
s = []
for i in range(2):
    for j in range(n):
        a = int(input())
        s.append((a, i))
s.sort()

ans = 1
l = []
cur = None
for num, c in s:
    if not l:
        l.append(s[i])
        cur = c
    elif c == cur:
        l.append(num)
    else:
        ans *= len(l)
        ans %= mod
        l.pop()
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=1
mod=10**9+7
A=[0,0]
AB=[]
for i in range(n):
  a=int(input())
  AB.append((a,0))
for i in range(n):
  b=int(input())
  AB.append((b,1))
AB.sort(key=lambda x:x[0])
for i in range(2*n):
  a,b=AB[i]
  if b==0:
    if A[1]>0:
      ans=(ans*A[1])%mod
      A[1]-=1
    else:
      A[0]+=1
  else:
    if A[0]>0:
      ans=(ans*A[0])%mod
      A[0]-=1
    else:
      A[1]+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())
lines = sys.stdin.readlines()
aaa = list(map(int, lines[:n]))
bbb = list(map(int, lines[n:]))
coords = [(a, 0) for a in aaa] + [(b, 1) for b in bbb]
coords.sort()
MOD = 10 ** 9 + 7

remain_type = 0
remain_count = 0
ans = 1
for x, t in coords:
    if remain_type == t:
        remain_count += 1
        continue
    if remain_count == 0:
        remain_type = t
        remain_count = 1
        continue
    ans = ans * remain_count % MOD
    remain_count -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
import bisect
def isprime(n):
  if n <= 1:
    return False
  else:
    for i in range(2,(int(n**0.5)+2)):
      if n%i == 0:
        return False
    return True

def solve():
  n = int(input())
  a = sorted([int(input()) for _ in range(n)])+[10**9 + 1]
  b = sorted([int(input()) for _ in range(n)])+[10**9 + 1]
  mod = 10**9+7
  ans = 1
  if n == 1:
    print(1)
  else:
    na,nb = 0,0
    for i in range(2*n):
      if na>nb and a[na]>b[nb]:
        ans *= na-nb
        ans %= mod
      elif na<nb and a[na]<b[nb]:
        ans *= nb-na
        ans %= mod
      
      if a[na] < b[nb]:na += 1
      else:nb += 1
  print(ans)
      
    
solve()

Submission status: Accepted

Solution code:
N,*E=map(int,open(0).read().split())
a,c=1,0
for _,d in sorted((e,2*(i<N)-1)for i,e in enumerate(E)):
	if c*d<0:a=abs(a*c)%(10**9+7)
	c+=d
print(a)

Submission status: Accepted

Solution code:
N,*E=map(int,open(0).read().split())
E=sorted((e,2*(i<N)-1)for i,e in enumerate(E))
a,c=1,0
for _,d in E:
	if c*d<0:a=abs(a*c)%(10**9+7)
	c+=d
print(a)

Submission status: Accepted

Solution code:
N,*E=map(int,open(0).read().split())
E=sorted((e,2*(i<N)-1)for i,e in enumerate(E))
a,c=1,0
for _,d in E:
	if c*d<0:a=(a*abs(c))%(10**9+7)
	c+=d
print(a)

Submission status: Accepted

Solution code:
N,*E=map(int,open(0).read().split())
E=sorted((e,2*(i<N)-1)for i,e in enumerate(E))
a,c=1,0
for _,d in E:
	if c*d<0:
		a=(a*abs(c))%(10**9+7)
	c+=d
print(a)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N, *E = map(int, open(0).read().split())
E = sorted((e, 2 * (i < N) - 1) for i, e in enumerate(E))

res = 1
cnt = 0
for _, delta in E:
    if cnt * delta < 0:
        res *= abs(cnt)
        res %= mod
    cnt += delta

print(res)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N, *E = map(int, open(0).read().split())
E = sorted((e, 1 if i < N else -1) for i, e in enumerate(E))

res = 1
cnt = 0
for _, delta in E:
    if cnt * delta < 0:
        res *= abs(cnt)
        res %= mod
    cnt += delta

print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

mod = 10 ** 9 + 7

N, *E = map(int, open(0).read().split())
E = sorted((e, 1 if i < N else -1) for i, e in enumerate(E))

res = 1
cnt = 0
for _, delta in E:
    if cnt * delta < 0:
        res *= abs(cnt)
        res %= mod
    cnt += delta

print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

mod = 10 ** 9 + 7

N, *E = map(int, open(0).read().split())
Q = []
for i, e in enumerate(E):
    heappush(Q, (e, 1 if i < N else -1))

res = 1
cnt = 0
while Q:
    _, delta = heappop(Q)
    if cnt * delta < 0:
        res *= abs(cnt)
        res %= mod
    cnt += delta

print(res)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())
A = [(int(input()), 1) for _ in range(N)]
B = [(int(input()), -1) for _ in range(N)]

C = sorted(A + B)

res = 1
cnt = 0
for _, delta in C:
    if cnt * delta < 0:
        res *= abs(cnt)
        res %= mod
    cnt += delta

print(res)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())
A = [(int(input()), -1) for _ in range(N)]
B = [(int(input()), 1) for _ in range(N)]

C = sorted(A + B)

res = 1
cnt = 0
for _, delta in C:
    if cnt != 0 and cnt * delta < 0:
        res *= abs(cnt)
        res %= mod
    cnt += delta

print(res)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())
A = [(int(input()), -1) for _ in range(N)]
B = [(int(input()), 1) for _ in range(N)]

C = sorted(A + B)

res = 1
cnt = 0
for _, delta in C:
    if cnt != 0 and (cnt > 0) != (delta > 0):
        res *= abs(cnt)
        res %= mod
    cnt += delta

print(res)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())
A = [(int(input()), False) for _ in range(N)]
B = [(int(input()), True) for _ in range(N)]

C = sorted(A + B)

res = 1
cnt = 0
for _, ab in C:
    delta = 1 if ab else -1
    if cnt != 0 and (cnt > 0) != ab:
        res *= abs(cnt)
        res %= mod
    cnt += delta

print(res)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
INF = 10 ** 10

N = int(input())
A = [int(input()) for _ in range(N)] + [INF]
B = [int(input()) for _ in range(N)] + [INF]

A.sort()
B.sort()

ans = 1
a = b = 0
i = j = 0
while i < N or j < N:
    if A[i] < B[j]:
        if b > 0:
            ans *= b
            b -= 1
        else:
            a += 1
        i += 1
    else:
        if a > 0:
            ans *= a
            a -= 1
        else:
            b += 1
        j += 1

    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [(int(input()), "a") for i in range(n)]
b = [(int(input()), "b") for i in range(n)]
li = sorted((a+b))
MOD = 10**9 + 7

def solve(li):
    ans = 1
    for i in range(len(li) - 1):
        if abs(li[i]) < abs(li[i+1]):
            ans *= abs(li[i+1])
            ans %= MOD
    return ans

num = 0
ans = 1
tmp = []
for i in range(2*n):
    if li[i][1] == "a":
        num += 1
    else:
        num -= 1
    if num == 0:
        ans *= solve(tmp)
        ans %= MOD
        tmp = []
    else:
        tmp.append(num)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
ab = []

for i in range(N):
    a = inp()
    ab.append([a,1])

for i in range(N):
    b = inp()
    ab.append([b,-1])

ab.sort()
cnt = 0
ans = 1
for x,k in ab:
    cnt += k
    if (cnt > 0) and (k > 0):
        ans *= cnt
    elif (cnt < 0) and (k < 0):
        ans *= -cnt
    ans %= mod
    
print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10 ** 9 + 7
A = []
B = []
for i in range(N):
    A.append((int(input()), 0))

for i in range(N):
    B.append((int(input()), 1))
D = A + B
D = sorted(D)

a = 0
b = 0
ans = 1
for x, i in D:
    if i == 0:
        if b == 0:
            a += 1
        else:
            ans *= b
            b -= 1
    else:
        if a == 0:
            b += 1
        else:
            ans *= a
            a -= 1
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
arr=[(int(input()),i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      ans*=cntb
      ans%=mod
      cntb-=1
  else:
    if cnta==0:
      cntb+=1
    else:
      ans*=cnta
      ans%=mod
      cnta-=1
print(ans)

Submission status: Accepted

Solution code:
# cf16-exhibition-final-openA - 1D Matching
import sys
input = sys.stdin.readline

def calc(x, y, total):
    MOD = 10 ** 9 + 7
    if y:
        total = (total * y) % MOD
        y -= 1
    else:
        x += 1
    return x, y, total

def main():
    N = int(input())
    A = tuple(map(int, [input() for _ in range(N)]))
    B = tuple(map(int, [input() for _ in range(N)]))
    C = sorted([(i, 1) for i in A] + [(i, 0) for i in B])
    ans, a, b = 1, 0, 0
    for i, t in C:
        if t:  # laptop
            a, b, ans = calc(a, b, ans)
        else:  # power sources
            b, a, ans = calc(b, a, ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
E = []
for _ in range(N):
    E += [(int(input()), 1)]
for _ in range(N):
    E += [(int(input()), -1)]
E.sort()
mod = 10**9 + 7
ans = 1
ab = 0
for e in E:
    if e[1] * ab < 0:
        ans *= abs(ab)
        ans %= mod
    ab += e[1]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(int(input())for _ in'_'*N)
A+=10**10,
B=sorted(int(input())for _ in'_'*N)
B+=10**10,
z=1
a=b=i=j=0
M=10**9+7
while i<N or j<N:
	if A[i]<B[j]:
		if b:
			z=z*b%M
			b-=1
		else:
			a+=1
		i+=1
	else:
		if a:
			z=z*a%M
			a-=1
		else:
			b+=1
		j+=1
print(z)

Submission status: Accepted

Solution code:
p=1
m=10**9+7
s=[0]*2
n=int(input())
q=sorted([[int(input()),i//n]for i in range(2*n)])
for i in q:
    if s[1-i[1]]==0:
        s[i[1]]+=1
    else:
        p=(p*s[1-i[1]])%m
        s[1-i[1]]-=1
print(p)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

mod = 10 ** 9 + 7

n = int(input())
a = [int(input()) for _ in range(n)]
b = [int(input()) for _ in range(n)]

h = []
for aa in a:
    heappush(h, (aa, True))
for bb in b:
    heappush(h, (bb, False))

ca = 0
cb = 0
ans = 1
while h:
    pos, is_elm_of_a = heappop(h)
    if is_elm_of_a:
        if cb > 0:
            ans *= cb
            ans %= mod
            cb -= 1
        else:
            ca += 1
    else:
        if ca > 0:
            ans *= ca
            ans %= mod
            ca -= 1
        else:
            cb += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(input())
A,B = [[int(input()) for _ in range(N)] for _ in [0,1]]

AB = [(x,0) for x in A] + [(x,1) for x in B]
AB.sort()

a = 0
b = 0
answer = 1
for x,i in AB:
    if i == 0:
        if b == 0:
            a += 1
            continue
        answer *= b
        b -= 1
    else:
        if a == 0:
            b += 1
            continue
        answer *= a
        a -= 1
    answer %= MOD

print(answer)

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline

MOD = int(1e9+7)


def main():
    N = int(input())
    P = [None] * N * 2
    for i in range(N):
        a = int(input())
        P[i] = (a, 0)
    for i in range(N):
        b = int(input())
        P[i+N] = (b, 1)
    P.sort(itemgetter(0))
    cand = [0] * 2
    ans = 1
    for p in P:
        cur = p[1]
        peer = cur ^ 1
        if cand[peer]:
            ans = (ans * cand[peer]) % MOD
            cand[peer] -= 1
        else:
            cand[cur] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
*A, = [(int(input()),1) for _ in [0]*N]
*B, = [(int(input()),-1) for _ in [0]*N]

mod = 10**9+7
fact = [1]*(N+1)
for i in range(N):
    fact[i+1] = fact[i]*(i+1)%mod

AB = A+B
AB.sort()
ans = 1
c = 0
d = 0
for l,ab in AB:
    if d*ab<0:
        ans *= abs(d)
        ans %= mod
    d += ab
    c += 1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n = int(input())
nodes = []
for i in range(n):
    nodes.append([int(input()), 0])
for i in range(n):
    nodes.append([int(input()), 1])

nodes.sort()
ans = 1
cnt = 0
state = 0
for x, label in nodes:
    if cnt == 0:
        cnt += 1
        state = label
    else:
        if state == label:
            cnt += 1
        else:
            ans *= cnt
            ans %= MOD
            cnt -= 1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n = int(input())
a = []
for _ in range(n):
	x = int(input())
	a.append([x, 1])
for _ in range(n):
	x = int(input())
	a.append([x, -1])
a.sort()
ans = 1
tmp = 0
for i in range(2*n):
	x = a[i][1]
	if x == 1 and tmp < 0:
		ans *= -tmp
	elif x == -1 and tmp > 0:
		ans *= tmp
	tmp += x
	ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
pat = 1
mod = 10**9+7
l = []
for _ in range(n):
  a = int(input())
  l.append((a,0))
for _ in range(n):
  a = int(input())
  l.append((a,1))
l.sort()
cur = {0:0, 1:0}
for x in l:
  if cur[1-x[1]]:
    pat = pat*cur[1-x[1]]%mod
    cur[1-x[1]] -= 1
  else:
    cur[x[1]] += 1
print(pat)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
AB=[(INT(), 'pc') for i in range(N)]+[(INT(), 'plug') for i in range(N)]
AB.sort()

C=Counter()
ans=1
for i in range(N*2):
    a,_type=AB[i]
    if C['pc']==C['plug']:
        C[_type]+=1
    elif C['pc']>C['plug']:
        if _type=='pc':
            C['pc']+=1
        else:
            ans=(ans*C['pc'])%MOD
            C['pc']-=1
    elif C['pc']<C['plug']:
        if _type=='plug':
            C['plug']+=1
        else:
            ans=(ans*C['plug'])%MOD
            C['plug']-=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
alist = list(reversed(sorted([int(input()) for _ in range(n)])))
blist = list(reversed(sorted([int(input()) for _ in range(n)])))
INF = pow(10, 9) + 7
a = alist.pop()
b = blist.pop()
aset, bset = 0, 0
ans = 1
while len(alist) > 0 or len(blist) > 0:
  if a < b:
    if bset > 0:
      ans = (ans * bset) % INF
      bset -= 1
    else:
      aset += 1
    a = INF
    if len(alist) > 0:
      a = alist.pop()
  else:
    if aset > 0:
      ans = (ans * aset) % INF
      aset -= 1
    else:
      bset += 1
    b = INF
    if len(blist) > 0:
      b = blist.pop()
print(ans % INF)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
data=[]
ans=1
mod=10**9+7
for i in range(N):
    data.append(('a',int(input())))
for i in range(N):
    data.append(('b',int(input())))
cnt=0
bef=data[0][0]
data.sort(key=lambda x:x[1])
for d in data:
    if cnt==0:
        bef=d[0]
        cnt+=1
    elif bef==d[0]:
        cnt+=1
    elif bef!=d[0]:
        ans=(ans*cnt)%mod
        cnt-=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
B = [int(input()) for _ in range(N)]
mod = 10**9+7

from bisect import bisect_right as br
from bisect import bisect_left  as bl

A.sort(reverse=True)
B.sort(reverse=True)


ans = 1

def mbr(ls, a):
    ok = N
    ng = 0
    mid = (ok+ng)//2
    while abs(ok-ng) > 1:
        if ls[mid] >= a:
            ng = mid
        else:
            ok = mid
        mid = (ok+ng)//2

    return ok

for i in range(N):
    a,b = A[i], B[i]
    if a > b:
        idx = mbr(A,b)
        ans = ans * (idx-i) % mod
    else:
        idx = mbr(B,a)
        ans = ans * (idx-i) % mod
print( ans % mod)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
a = []
b = []
bb = []

for i in range(N):
	a.append(int(input()))

for i in range(N):
	b.append(int(input()))

a = sorted(a)
b = sorted(b)

for i in range(N):
	bb.append(bisect.bisect_left(a, b[i]))

ans = 1
for i in range(N):
	if bb[i] - i != 0:
		if bb[i] > i:
			ans = ans * (bb[i] - i)
		else:
			ans = ans * (i - bb[i] + 1)
		ans = ans % 1000000007

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for n in range(N)]
B = [int(input()) for n in range(N)]
A.sort()
B.sort()
A.append(10**10) #門番
B.append(10**10) #門番
mod = 7 + 10**9
ANU, BNU = 0, 0 #A not used, B not used
Total = 1
 
ai, bi = 0, 0
if A[0] < B[0]:
    ANU += 1
    ai += 1
else:
    BNU += 1
    bi += 1
while ai < N or bi < N:
    if A[ai] < B[bi]:
        if BNU == 0:
            ANU += 1
        else:
            Total *= BNU
            Total %= mod
            BNU -= 1
        ai += 1
    else:
        if ANU == 0:
            BNU += 1
        else:
            Total *= ANU
            Total %= mod
            ANU -= 1
        bi += 1
print(Total)

Submission status: Accepted

Solution code:
import sys

MOD = 10**9 + 7

N = int(input())
As = [int(sys.stdin.readline()) for _ in range(N)] + [10**9 + 1]
Bs = [int(sys.stdin.readline()) for _ in range(N)] + [10**9 + 1]

As.sort()
Bs.sort()

ans = 1
iA = iB = 0
for _ in range(2*N):
    if iA > iB and As[iA] > Bs[iB]:
        ans *= iA - iB
        ans %= MOD
    elif iA < iB and As[iA] < Bs[iB]:
        ans *= iB - iA
        ans %= MOD

    if As[iA] < Bs[iB]:
        iA += 1
    else:
        iB += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [(int(input()), 0) for i in range(N)]
B = [(int(input()), 1) for i in range(N)]
mod = 10 ** 9 + 7


X = A + B
X.sort()


ans = 1
Ar, Br = 0, 0

for x, i in X:
    if i == 0:
        if Br > 0:
            ans *= Br
            ans %= mod
            Br -= 1
        else:
            Ar += 1

    else:
        if Ar > 0:
            ans *= Ar
            ans %= mod
            Ar -= 1
        else:
            Br += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = []
for i in range(N):
  L.append((int(input()),'a'))
for i in range(N):
  L.append((int(input()),'b'))
L.sort()
res = 1
cc = 0
nowcol = None
mo = 1000000007
for i in range(2*N):
  if cc == 0:
    nowcol=L[i][1]
  if nowcol == L[i][1]:
    cc += 1
  else:
    res *= cc
    res %= mo
    cc -= 1
print(res)

Submission status: Accepted

Solution code:
N=int(input())
C=[]
for i in range(N):
  C.append((int(input()),"a")) 
for i in range(N):
  C.append((int(input()),"b")) 
C.sort()
mod=10**9+7
a,b=0,0
ans=1
for c in C:
  if c[1]=="a":
    if b>0:
      ans=(ans*b)%mod
      b-=1
    else:
      a+=1
  if c[1]=="b":
    if a>0:
      ans=(ans*a)%mod
      a-=1
    else:
      b+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9 + 7

a = [(int(input()), 0) for _ in range(N)]
b = [(int(input()), 1) for _ in range(N)]
ab = sorted(a+b, key = lambda x: x[0])
ans = 1
stack = []
for i, j in ab:
    if stack and stack[-1] != j:
        ans = ans * len(stack) %mod
        stack.pop()
    else:
        stack.append(j)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
mod=10**9+7
for i in range(N):
    a=int(input())
    A.append((a,-1))
for i in range(N):
    a=int(input())
    A.append((a,1))
A.sort()
a=0
s=A[0][1]
ans=1
for i in range(2*N):
    if A[i][1]==s:
        a+=1
    else:
        ans*=a
        ans%=mod
        a-=1
    if a==0 and i<2*N-1:
        s=A[i+1][1]
    #print(a,s,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

MOD = 10**9+7

devices = []

n = ni()
for _ in range(n):
    a = ni()
    devices.append((a, 1))
    
for _ in range(n):
    b = ni()
    devices.append((b, -1))
    
devices.sort()

pc = [0,0]

ans = 1
for point, typ in devices:
    if typ == 1 and pc[1] > 0:
        ans = (ans * pc[1]) % MOD
        pc[1] -= 1
        
    elif typ == 1:
        pc[0] += 1
        
    elif typ == -1 and pc[0] > 0:
        ans = (ans * pc[0]) % MOD
        pc[0] -= 1
        
    elif typ == -1:
        pc[1] += 1
        
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
L = []
for _ in range(N):
    L.append([int(input()), 0])
for _ in range(N):
    L.append([int(input()), 1])
L.sort()
a = 0
b = 0
ans = 1
for val, ab in L:
    if ab==0:
        if b>0:
            ans = ans * b % mod
            b-=1
        else:
            a+=1
    else:
        if a>0:
            ans = ans * a % mod
            a-=1
        else:
            b+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [('a',int(input())) for _ in range(n)]
b = [('b',int(input()))for _ in range(n)]
ab = sorted(a+b, key=lambda x: x[1])
m = []
count = 0
for k,i in ab:
    if k == 'a':
        if count < 0:
            m.append(-count)
        count += 1
    else:
        if count > 0:
            m.append(count)
        count -= 1
ans = 1
for mm in m:
    ans *= mm
    ans %= 10**9+7
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
points = []
for i in range(N):
    a = int(input())
    points.append([a,True])
for i in range(N):
    b = int(input())
    points.append([b,False])
points.sort()

ans = 1
an = bn = 0
for x,c in points:
    if c:
        if bn > 0:
            ans = (ans*bn)%mod
            bn -= 1
        else:
            an += 1
    else:
        if an > 0:
            ans = (ans*an)%mod
            an -= 1
        else:
            bn += 1

print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
a = [(int(input()), 1) for _ in range(N)]
b = [(int(input()), 0) for _ in range(N)]
X = sorted(a + b)

mod = 10 ** 9 + 7
ls = 0
stack = []
ans = 1
for v, f in X:
    if stack and stack[-1] != f:
        ans = ans * ls % mod
        stack.pop()
        ls -= 1
    else:
        stack.append(f)
        ls += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [(int(input()), 0) for i in range(N)]
B = [(int(input()), 1) for i in range(N)]
Object = sorted(A + B)
mod = 10 ** 9 + 7

ans = 1
memo = [0, 0]
for n, x in Object:
    if memo[1 - x] > 0:
        ans = (ans * memo[1 - x]) % mod
        memo[1 - x] -= 1
    else:
        memo[x] += 1

print(ans)

Submission status: Accepted

Solution code:
from bisect import *

n = int(input())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i] = int(input())
for i in range(n):
    b[i] = int(input())

a.sort()
b.sort()

ans = 1
mod = 1000000007

for x,y in zip(a,b):
    if x > y:
        x, y = y, x
    ans *= (bisect_right(a, y)-bisect_left(a, x))
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
src = []
for i in range(2*N):
    src.append((int(input()), i//N))

ans = 1
MOD = 10**9+7
mem = [0, 0]
for a,t in sorted(src):
    if mem[1-t] > 0:
        ans = (ans * mem[1-t]) % MOD
        mem[1-t] -= 1
    else:
        mem[t] += 1
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
from collections import deque
mod=10**9+7
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
b=[int(raw_input()) for _ in xrange(n)]
d={}
a.sort()
b.sort()
ab=sorted(a+b)
for i in xrange(n):
    d[a[i]]="a"
    d[b[i]]="b"

stack=deque()
ans=1
for i in xrange(2*n):
    if len(stack)==0:
        stack.append(d[ab[i]])
        continue
    if d[ab[i]]=="a":
        if stack[-1]=="a":
            stack.append("a")
        else:
            ans=ans*len(stack)%mod
            stack.popleft()
    if d[ab[i]]=="b":
        if stack[-1]=="b":
            stack.append("b")
        else:
            ans=ans*len(stack)%mod
            stack.popleft()
print ans

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
n = input()
ps = [(int(raw_input()), i<n) for i in xrange(2*n)]
ps.sort()

MOD = 10**9+7
cnt = 0
ans = 1
for p, v in ps:
    if v == 0:
        if cnt > 0:
            ans *= cnt
            ans %= MOD
        cnt -= 1
    else:
        if cnt < 0:
            ans *= -cnt
            ans %= MOD
        cnt += 1
print ans

Submission status: Runtime Error

Solution code:
n=int(input())
arr=[(int(input()),i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      cntb-=1
  else:
    if cnta>=1:
      ans*=cnt
      ans%=mod
      cnta-=1
    else:
      cntb+=1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
arr=[(int(input()),i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      cntb-=1
  else:
    if cnta>=1:
      ans*=cnt
      ans%=mod
      cnt-=1
    else:
      cntb+=1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
arr=[(int(input())+i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      cntb-=1
  else:
    if cnta>=1:
      ans*=cnt
      ans%=mod
      cnt-=1
    else:
      cntb+=1
print(ans)