Problem:


Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points.
The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

All input values are integers.

1 \leq N \leq 100

0 \leq a_i, b_i, c_i, d_i < 2N

a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.

b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

Output

Print the maximum number of friendly pairs.

Sample Input 1

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

2

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Sample Input 2

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

2

For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

Sample Output 4

5

Sample Input 5

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

Sample Output 5

4



Sample input:
3
2 0
3 1
1 3
4 2
0 4
5 5


Sample output:
2

Submission status: Accepted

Solution code:
n = int(input())
red  = [tuple(map(int, input().split())) for _ in range(n)]
blue = [tuple(map(int, input().split())) for _ in range(n)]

red.sort(key=lambda x:x[1])
blue.sort()

count = 0
for xb, yb in blue:
    max_y = -1
    max_i = -1
    for i in range(n):
        xr, yr = red[i]
        if xb > xr and yb > yr and max_y < yr:
            max_y, max_i = yr, i
    if max_y >= 0:
        red[max_i] = (201, 201)
        count += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]
red.sort(reverse=True)
blue.sort(key=lambda x:x[1])
blue_check = [0]*N
for i in range(N):
    for k in range(N):
        if blue_check[k] == 1:
            continue
        if red[i][0] < blue[k][0] and red[i][1] < blue[k][1]:
            blue_check[k] = 1
            break
print(sum(blue_check))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
N = int(input())
A = []
for i in range(N):
    A.append(tuple(map(int, input().split())))
A.sort()

B = []
for i in range(N):
    B.append(tuple(map(int, input().split())))
B.sort()

heap = []
heapify(heap)
aindex = count = 0
for b in B:
    while aindex < len(A) and A[aindex][0] < b[0]:
        heappush(heap, -A[aindex][1])
        aindex += 1
    buf = []
    while heap and b[1] <= -heap[0]:
        ay = heappop(heap)
        buf.append(ay)
    if heap and -heap[0] < b[1]:
        count += 1
        heappop(heap)
    for ay_ in buf:
        heappush(heap, ay_)
print(count)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
import networkx as nx
def resolve():
    n = int(input())
    A = [tuple(map(int, input().split())) for _ in range(n)]
    B = [tuple(map(int, input().split())) for _ in range(n)]
    G = nx.Graph()
    G.add_nodes_from(range(n))
    G.add_nodes_from(range(n, 2 * n))
    for i in range(n):
        ax, ay = A[i]
        for j in range(n):
            bx, by = B[j]
            if ax < bx and ay < by:
                G.add_edge(i, n + j)

    A = nx.algorithms.bipartite.maximum_matching(G, top_nodes = range(n))
    print(len(A) // 2)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
import networkx as nx
def resolve():
    n = int(input())
    A = [tuple(map(int, input().split())) for _ in range(n)]
    B = [tuple(map(int, input().split())) for _ in range(n)]
    G = nx.Graph()
    G.add_nodes_from(range(n))
    G.add_nodes_from(range(n, 2 * n))
    for i in range(n):
        ax, ay = A[i]
        for j in range(n):
            bx, by = B[j]
            if ax < bx and ay < by:
                G.add_edge(i, n + j)

    A = nx.algorithms.bipartite.matching.hopcroft_karp_matching(G, top_nodes = range(n))
    print(len(A) // 2)
resolve()

Submission status: Accepted

Solution code:
N = int(input())
Red = [[int(T) for T in input().split()] for TN in range(0,N)]
Red.sort(key=lambda X:X[1],reverse=True)
Blue = [[int(T) for T in input().split()] for TN in range(0,N)]
Blue.sort(key=lambda X:X[0])
Count = 0

for TB in range(0,N):
    DelInd = -1
    for TR in range(0,len(Red)):
        if Blue[TB][0]>Red[TR][0] and Blue[TB][1]>Red[TR][1]:
            DelInd = TR
            break
    if DelInd!=-1:
        del Red[DelInd]
        Count += 1
print(Count)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import maximum_bipartite_matching
def resolve():
    n = int(input())
    A = [tuple(map(int, input().split())) for _ in range(n)]
    B = [tuple(map(int, input().split())) for _ in range(n)]

    weights = []
    rows = []
    columns = []
    for i in range(n):
        ax, ay = A[i]
        for j in range(n):
            bx, by = B[j]
            if ax < bx and ay < by:
                weights.append(1)
                rows.append(i)
                columns.append(j)

    graph = coo_matrix((weights, (rows, columns)), shape = (n, n))
    ans = sum(maximum_bipartite_matching(graph) >= 0)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_bipartite_matching
def resolve():
    n = int(input())
    A = [tuple(map(int, input().split())) for _ in range(n)]
    B = [tuple(map(int, input().split())) for _ in range(n)]

    graph = csr_matrix([[int(A[i][0] < B[j][0] and A[i][1] < B[j][1]) for j in range(n)] for i in range(n)])
    ans = 0
    for a in maximum_bipartite_matching(graph):
        if a != -1:
            ans += 1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    red = []
    red_used = [[False for _ in range(2 * n)] for _ in range(2 * n)]
    for _ in range(n):
        rp = list(map(int, input().split()))
        red.append(rp)
        red_used[rp[0]][rp[1]] = True
    ans = 0
    red.sort(key=lambda x: x[1], reverse=True)
    blue = [list(map(int, input().split())) for _ in range(n)]
    blue.sort(key=lambda x: x[0])
    for bx, by in blue:
        for rx, ry in red:
            if rx < bx and ry < by and red_used[rx][ry]:
                red_used[rx][ry] = False
                ans += 1
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import networkx as nx

n = int(input())
graph = nx.DiGraph()
AB = [list(map(int, input().split())) for _ in range(n)]
CD = [list(map(int, input().split())) for _ in range(n)]

start = 10 ** 4
goal = 10 ** 4 + 1
for i in range(n):
    a, b = AB[i]
    graph.add_edge(start, i, weight=0, capacity=1)
    for j in range(n):
        c, d = CD[j]
        graph.add_edge(200 + j, goal, weight=0, capacity=1)
        if c > a and d > b:
            graph.add_edge(i, 200 + j, weight=0, capacity=1)

ans = nx.maximum_flow(graph, start, goal, capacity="capacity")
print(ans[0])

Submission status: Accepted

Solution code:
n=int(input())
r=[tuple(map(int,input().split())) for _ in range(n)]
b=[tuple(map(int,input().split())) for _ in range(n)]
r=sorted(r)
b=sorted(b)
for x,y in b:
  p,q=-1,-1
  for i,j in r:
    if i<x and j<y and j>q:p,q=i,j
  if (p,q) in r:r.remove((p,q))
print(n-len(r))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    P = [0] * (2 * N)
    for i in range(N):
        a, b = map(int, readline().split())
        P[i] = (a, b, 0)
    for i in range(N, 2 * N):
        c, d = map(int, readline().split())
        P[i] = (c, d, 1)

    P.sort(reverse=True)

    vec = [0] * (2 * N + 1)
    ans = 0

    for x, y, p in P:
        if p == 0:
            for i in range(y + 1, 2 * N + 1):
                if vec[i] > 0:
                    vec[i] -= 1
                    ans += 1
                    break
        else:
            vec[y] += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import networkx as nx

N=int(input())
ab=[list(map(int,input().split())) for _ in range(N)]
ab=sorted(ab)
cd=[list(map(int,input().split())) for _ in range(N)]
cd=sorted(cd,reverse=True)

G = nx.DiGraph()
for i in range(N):
  G.add_edge('x',i, capacity=1)
  for j in range(N):
    if i == 0:
      G.add_edge(N+j,'y', capacity=1)
    a,b=ab[i]
    c,d=cd[j]
    if a<c and b<d:
      G.add_edge(i,N+j, capacity=1)
    elif a>=c:break

flow_value, flow_dict = nx.maximum_flow(G, 'x', 'y')
print(flow_value)

Submission status: Accepted

Solution code:
n = int(input())
red = [list(map(int, input().split())) for _ in range(n)]
blue = [list(map(int, input().split())) for _ in range(n)]

blue.sort()

res = 0
for bx, by in blue:
    dist = -1
    for rx, ry in red:
        if rx < bx and dist < ry < by:
            dist = ry
            mx, my = rx, ry
    
    if dist > -1:
        res += 1
        red.remove([mx, my])

print(res)

Submission status: Accepted

Solution code:
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
cd = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda x: (-x[1], x[0]))
cd.sort(key=lambda x: (x[0], x[1]))
s = [0] * n

for i in range(n):
    for j in range(n):
        if s[j] == 0 and ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1]:
            s[j] = 1
            break
print(sum(s))

Submission status: Accepted

Solution code:
N = int(input())
R = []
B = []
for i in range(2 * N):
    a, b = map(int, input().split())
    if i < N:
        R.append((a, b))
    else:
        B.append((a, b))
B = sorted(B)

ans = 0
checked = set()
p = []
for b in B:
    x1, y1 = b
    tR = [(x2, y2) for x2, y2 in R if x2 < x1]
    tR = sorted(tR, key=lambda p: p[1], reverse=True)
    for x2, y2 in tR:
        if (x2, y2) in checked:
            continue
        if x1 > x2 and y1 > y2:
            ans += 1
            checked.add((x2, y2))
            p.append((b, (x2, y2)))
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ab = [[int(i) for i in input().split()] for _ in range(N)]
cd = [[int(i) for i in input().split()] for _ in range(N)]

ab.sort(key = lambda x: x[1], reverse=True)
cd.sort()

x = 0
for c, d in cd:
    for a, b in ab:
        if a < c and b < d:
            x += 1
            ab.remove([a, b])
            break

print(x)

Submission status: Accepted

Solution code:
from operator import itemgetter
N=int(input())
R=[list(map(int,input().split())) for n in range(N)]
B=[list(map(int,input().split())) for n in range(N)]
R.sort(key=itemgetter(1),reverse=True)
B.sort()
ans=0

for c,d in B :
    for a,b in R :
        if a<c and b<d :
            ans+=1
            R.remove([a,b])
            break

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
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

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

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

N = getN()
# Rはループさせるのでソートさせる必要ない
R = [getList() for i in range(N)]
R_l = [1] * N

B = [getList() for i in range(N)]
B.sort()

# 貪欲法でペア作りする問題
# ABC005 C - おいしいたこ焼きの売り方の時と同様に
# それとしか繋げないもの　を優先的に繋いでいく

# 条件Aの通過が厳しい順に対象bをソートし、
# たこ焼き　条件A:客が来る前にたこ焼きができてないといけない
#  　　　　      客を来るのが早い順に並べる（最初から並んでる）
# 今回     条件A:赤星のx座標が青星のx座標より小さくないといけない
#  　　　　　　　 青星をx座標が小さい順に並べる

# 条件A, 条件Bをクリアしたものの中で、最も条件Bの通過が厳しい対象aと結ぶ
# たこ焼き　条件B:たこ焼きが賞味期限より前のものでないといけない
#  　　　　      できるだけ古いものを売る（最初から並んでる）
# 今回     条件B:赤星のy座標が青星のy座標より小さくないといけない
#  　　　　　　　 条件をクリアしたもののうちでできるだけy座標が大きいものを選ぶ

ans = 0
for b in B:
    max_y = -1
    max_index = -1
    for i, a in enumerate(R):
        # x, y座標が小さいもののうちでまた使ってないもの
        if a[0] < b[0] and a[1] < b[1] and R_l[i] == 1:
            # あるならY座標が最も大きいもの
            if a[1] > max_y:
                max_y = a[1]
                max_index = i
    if max_y >= 0:
        R_l[max_index] = 0
        ans += 1
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
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

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

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

N = getN()
# Rはループさせるのでソートさせる必要ない
R = [getList() for i in range(N)]
R_l = [1] * N

B = [getList() for i in range(N)]
B.sort()

# 貪欲法でペア作りする問題
# ABC005 C - おいしいたこ焼きの売り方の時と同様に
# それとしか繋げないもの　を優先的に繋いでいく

# 条件Aの通過が厳しい順に対象bをソートし、
# たこ焼き　条件A:客が来る前にたこ焼きができてないといけない
#  　　　　      客を来るのが早い順に並べる（最初から並んでる）
# 今回     条件A:赤星のx座標が青星のx座標より小さくないといけない
#  　　　　　　　 青星をx座標が小さい順に並べる

# 条件A, 条件Bをクリアしたものの中で、最も条件Bの通過が厳しい対象aと結ぶ
# たこ焼き　条件B:たこ焼きが賞味期限より前のものでないといけない
#  　　　　      できるだけ古いものを売る（最初から並んでる）
# 今回     条件B:赤星のx座標が青星のy座標より小さくないといけない
#  　　　　　　　 条件をクリアしたもののうちでできるだけy座標が大きいものを選ぶ

ans = 0
for b in B:
    max_y = -1
    max_index = -1
    for i, a in enumerate(R):
        # x, y座標が小さいもののうちてまた使ってないもの
        if a[0] < b[0] and a[1] < b[1] and R_l[i] == 1:
            # あるならY座標が最も大きいもの
            if a[1] > max_y:
                max_y = a[1]
                max_index = i
    if max_y >= 0:
        R_l[max_index] = 0
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N= int(input())
red=[list(map(int,input().split())) for i in range(N)]
red.sort()
blue=[list(map(int,input().split())) for i in range(N)]
blue.sort()
ans=0
from operator import itemgetter
for i in range(N):
   x,y=blue[i]
   l=[]
   for j in range(N):
      try:
         if x>red[j][0] and y>red[j][1]:
            l.append(red[j])
      except IndexError:
         break
   try:
      l.sort(key=itemgetter(1),reverse=True)
      red.remove(l[0])
   except IndexError:
      pass
print(N-len(red))

Submission status: Accepted

Solution code:
N = int(input())
R = [list(map(int,input().split())) for n in range(N)]
B = [list(map(int,input().split())) for n in range(N)]
R.sort(key=lambda x:-x[1])
B.sort()
ans=0

for c,d in B:
  for a,b in R:
    if a<c and b<d:
      ans+=1
      R.remove([a,b])
      break

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    goal = N*2+1
    edge = [set() for _ in range(goal+1)]

    red = [LI() for _ in range(N)]
    blue = [LI() for _ in range(N)]

    for i in range(1,N+1):
        edge[0].add(i)
    for i in range(N+1,goal):
        edge[i].add(goal)

    for i in range(N):
        a,b = red[i]
        for j in range(N):
            c,d = blue[j]
            if a < c and b < d:
                edge[i+1].add(N+j+1)

    ans = 0

    while True:
        q = collections.deque()
        node = [-1] * (goal + 1)
        node[0] = 0
        q.append(0)
        while q:
            u = q.pop()
            for v in edge[u]:
                if node[v] >= 0: continue
                node[v] = u
                if v == goal:
                    ans += 1
                    break
                q.append(v)
            else:
                continue
            break
        else:
            break

        v = goal
        while v > 0:
            u = node[v]
            edge[u].remove(v)
            edge[v].add(u)
            v = u

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
#   edges[x]: xとつながるYの頂点のset
#   matched[y]: yとマッチングされたXの頂点(暫定)
 
def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False
 
 
# 標準入力からのグラフ読み取り
N = int(input())
red_xy = [list(map(int,input().split())) for i in range(N)]
blue_xy = [list(map(int,input().split())) for i in range(N)]

edges = [set() for _ in range(N)]
matched = [-1] * N
 
for i in range(N):
    for j in range(N):
        #x, y = map(int, input().split())
        if red_xy[i][0] < blue_xy[j][0] and red_xy[i][1] < blue_xy[j][1]:
            edges[i].add(j)
 
# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(N)))

Submission status: Accepted

Solution code:
N = int(input())#100
AB = [0] * N
for i in range(N):
  AB[i] = list(map(int, input().split()))
AB = sorted(AB)
CD = [0] * N
for i in range(N):
  CD[i] = list(map(int, input().split()))
CD = sorted(CD)
#print(AB, CD)

ans = 0

used = [0] * N
for i in range(N):
  now_x, now_y = CD[i][0], CD[i][1]
  max_y = -1
  nn = -1
  for j in range(N):
    if (now_x > AB[j][0]) and (used[j] == 0):
      if now_y > AB[j][1]:
        if max_y < AB[j][1]:
          max_y = AB[j][1]
          nn = j
  if max_y != -1:
    ans += 1
    used[nn] = 1
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]
blue = sorted(blue, key=lambda x: x[0])

used = []
for i in range(N):
    c, d = blue[i]
    m, tmp = -1, -1
    for j in range(N):
        if j in used:
            continue
        a, b = red[j]
        if a < c and b < d:
            if b > m:
                m = b
                tmp = j
    if tmp != -1:
        used.append(tmp)
print(len(used))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    B = []
    g = [[0]*(2*n) for _ in range(2*n)]
    for _ in range(n):
        a,b  = map(int,input().split())
        g[b][a] = 1
    for _ in range(n):
        c,d = map(int,input().split())
        B.append((c,d))
    B.sort()
    ans = 0
    for i,j in B:
        f = 0
        for y in range(j,-1,-1):
            for x in range(i,-1,-1):
                if g[y][x]:
                    ans += 1
                    f = 1
                    g[y][x] = 0
                    break
            if f:
                break
    print(ans)

main()

Submission status: Accepted

Solution code:
N = int(input())
R = [[0, 0] for _ in range(N)]
B = [[0, 0] for _ in range(N)]
Map = [['.' for __ in range(2*N)] for _ in range(2*N)]
for i in range(N):
  R[i][1], R[i][0] = map(int, input().split())
  Map[R[i][1]][R[i][0]] = 'R'
for i in range(N):
  B[i][0], B[i][1] = map(int, input().split())
  Map[B[i][0]][B[i][1]] = 'B'
R.sort(reverse=True)
B.sort()
RF = [True for _ in range(N)]
BF = [True for _ in range(N)]
cnt = 0
for i in range(N):
  for j in range(N):
    if BF[j] == True:
      if R[i][1] < B[j][0] and R[i][0] < B[j][1]:
        cnt += 1
        RF[i] = False
        BF[j] = False
        break
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
red=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:x[1],reverse=True)
blue=sorted([list(map(int,input().split())) for i in range(n)])
ans=0
for bx,by in blue:
    for rx,ry in red:
        if rx<bx and ry<by:
            ans+=1
            red.remove([rx,ry])
            break
print(ans)

Submission status: Accepted

Solution code:
import collections, itertools, copy


class MaximumFlow:
    def __init__(self, G):
        self.G = G

    def ford_fulkerson(self, s, t):
        G = self.G
        G_residue = copy.deepcopy(G)

        def dfs(start, used):
            if start == t:
                return [start]
            for end, cap in G_residue[start].items():
                if cap > 0 and end not in used:
                    used.add(end)
                    ret = dfs(end, used)
                    if ret:
                        return ret + [start]
            return []

        flow_value = 0
        while True:
            root = dfs(s, set([s]))
            if root:
                root = root[::-1]
                residue = min(
                    [G_residue[a][b] for a, b in zip(root, root[1:])])
                flow_value += residue
                for a, b in zip(root, root[1:]):
                    G_residue[a][b] -= residue
                    G_residue[b][a] += residue
            else:
                flow_dict = collections.defaultdict(
                    lambda: collections.defaultdict(int))
                for a in G:
                    for b in G[a]:
                        if G_residue[b][a] > 0:
                            flow_dict[a][b] = G_residue[b][a]
                return (flow_value, flow_dict)


N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N)]
CD = [[int(_) for _ in input().split()] for _ in range(N)]
G = collections.defaultdict(lambda: collections.defaultdict(int))
for a, b in AB:
    G[-1][1000 * a + b] = 1
for c, d in CD:
    G[1000 * c + d][-2] = 1
for ab, cd in itertools.product(AB, CD):
    a, b = ab
    c, d = cd
    if a < c and b < d:
        G[1000 * a + b][1000 * c + d] = 1
flow_value, G_residue = MaximumFlow(G).ford_fulkerson(-1, -2)
print(flow_value)

Submission status: Accepted

Solution code:
import collections, itertools, copy


class MaximumFlow:
    def ford_fulkerson(self, G, s, t):
        G_residue = copy.deepcopy(G)

        def dfs(start, used):
            if start == t:
                return [start]
            for end, cap in G_residue[start].items():
                if cap > 0 and end not in used:
                    used.add(end)
                    ret = dfs(end, used)
                    if ret:
                        return ret + [start]
            return []

        flow_value = 0
        while True:
            root = dfs(s, set([s]))
            if root:
                root = root[::-1]
                residue = min(
                    [G_residue[a][b] for a, b in zip(root, root[1:])])
                flow_value += residue
                for a, b in zip(root, root[1:]):
                    G_residue[a][b] -= residue
                    G_residue[b][a] += residue
            else:
                return (flow_value, G_residue)


N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N)]
CD = [[int(_) for _ in input().split()] for _ in range(N)]
G = collections.defaultdict(lambda: collections.defaultdict(int))
for a, b in AB:
    G[-1][1000 * a + b] = 1
for c, d in CD:
    G[1000 * c + d][-2] = 1
for ab, cd in itertools.product(AB, CD):
    a, b = ab
    c, d = cd
    if a < c and b < d:
        G[1000 * a + b][1000 * c + d] = 1
flow_value, G_residue = MaximumFlow().ford_fulkerson(G, -1, -2)
print(flow_value)
flow_dict = collections.defaultdict(lambda: collections.defaultdict(int))
for a in G:
    for b in G[a]:
        if G_residue[b][a] > 0:
            flow_dict[a][b] = G_residue[b][a]

Submission status: Accepted

Solution code:
import collections, itertools, copy


class MaximumFlow:
    def ford_fulkerson(self, G, s, t):
        G_residue = copy.deepcopy(G)

        def dfs(start, used):
            if start == t:
                return [start]
            for end, cap in G_residue[start].items():
                if cap > 0 and end not in used:
                    used.add(end)
                    ret = dfs(end, used)
                    if ret:
                        return ret + [start]
            return []

        flow_value = 0
        while True:
            root = dfs(s, set([s]))
            if root:
                root = root[::-1]
                residue = min(
                    [G_residue[a][b] for a, b in zip(root, root[1:])])
                flow_value += residue
                for a, b in zip(root, root[1:]):
                    G_residue[a][b] -= residue
                    G_residue[b][a] += residue
            else:
                return (flow_value, G_residue)


N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N)]
CD = [[int(_) for _ in input().split()] for _ in range(N)]
G = collections.defaultdict(lambda: collections.defaultdict(int))
for a, b in AB:
    G[-1][1000 * a + b] = 1
for c, d in CD:
    G[1000 * c + d][-2] = 1
for ab, cd in itertools.product(AB, CD):
    a, b = ab
    c, d = cd
    if a < c and b < d:
        G[1000 * a + b][1000 * c + d] = 1
flow_value, flow_dict = MaximumFlow().ford_fulkerson(G, -1, -2)
print(flow_value)

Submission status: Accepted

Solution code:
n=int(input())
rs=[list(map(int,input().split())) for _ in range(n)]
bs=[list(map(int,input().split())) for _ in range(n)]
rs.sort(key=lambda x:x[1],reverse=True)
bs.sort()
ans=0
for c,d in bs:
    for a,b in rs:
        if a<c and b<d:
            ans+=1
            rs.remove([a,b])
            break
print(ans)

Submission status: Accepted

Solution code:
import collections, itertools


class MaximumFlow:
    def __init__(self, G):
        self.G = G

    def ford_fulkerson(self, s, t):
        def dfs(start, used):
            G = self.G
            if start == t:
                return [start]
            for end, cap in G[start].items():
                if cap > 0 and end not in used:
                    used.add(end)
                    ret = dfs(end, used)
                    if ret:
                        return ret + [start]
            return []

        fmax = 0
        cnt = 0
        while True:
            G = self.G
            cnt += 1
            root = dfs(s, set([s]))
            if root:
                root = root[::-1]
                residue = min([G[a][b] for a, b in zip(root, root[1:])])
                fmax += residue
                for a, b in zip(root, root[1:]):
                    G[a][b] -= residue
                    G[b][a] += residue
            else:
                return (fmax, G)


N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N)]
CD = [[int(_) for _ in input().split()] for _ in range(N)]
G = collections.defaultdict(lambda: collections.defaultdict(int))
for a, b in AB:
    G[-1][1000 * a + b] = 1
for c, d in CD:
    G[1000 * c + d][-2] = 1
for ab, cd in itertools.product(AB, CD):
    a, b = ab
    c, d = cd
    if a < c and b < d:
        G[1000 * a + b][1000 * c + d] = 1
flow = MaximumFlow(G)
fmax, Gres = flow.ford_fulkerson(-1, -2)
print(fmax)

Submission status: Accepted

Solution code:
N = int(input())
r = []
for i in range(N):
    r.append(list(map(int, input().split())))
b = []
for i in range(N):
    b.append(list(map(int, input().split())))
r = sorted(r, key=lambda x: x[0])
b = sorted(b, key=lambda x: x[0])
r_selected = [False] * N
ans = 0
for i in range(N):
    y_max = -1
    j_selected = -1
    for j in range(N):
        if r_selected[j]:
            continue
        if b[i][0] > r[j][0] and b[i][1] > r[j][1]:
            if y_max < r[j][1]:
                y_max = r[j][1]
                j_selected = j
    if y_max == -1:
        continue
    else:
        r_selected[j_selected] = True
print(r_selected.count(True))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from bisect import bisect_right
N = int(input())
ab = [list(mapint()) for _ in range(N)]
cd = [list(mapint()) for _ in range(N)]
ab.sort(reverse=True)
cd.sort(key=lambda x: x[1])
checked = [0]*N

ans = 0
for n in range(N):
    a, b = ab[n]
    for i in range(N):
        if checked[i]:
            continue
        c, d = cd[i]
        if a<c and b<d:
            ans += 1
            checked[i] = 1
            break

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import sys
    
    readline = sys.stdin.readline    # 1行だけ文字列にする

    N = int(readline())

    # 赤，青点をx,y座標の2次元リストとして入力
    red = [list(map(int, readline().split())) for _ in [0] * N]
    blue = [list(map(int, readline().split())) for _ in [0] * N]

    # 赤はy座標で降順ソート，青はx座標で昇順ソート
    red.sort(key=lambda x: x[1], reverse=True)
    blue.sort()

    ans = 0
    for c, d in blue:
        for a, b in red:
            if a <= c and b <= d:
                ans += 1
                red.remove([a, b])
                break
    print(ans)


resolve()