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:

import queue

class Dinic:
    """Implementation of Dinic's Alogorithm"""

    def __init__(self, v, inf = 1000000007):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0;
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0 : return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)


N, = [int(x) for x in input().strip().split(" ")]
dinic = Dinic(2 * N + 2)

import sys
rs = []
bs = []
for i in range(N):
    rs.append([int(x) for x in input().strip().split(" ")])
for i in range(N):
    bs.append([int(x) for x in input().strip().split(" ")])

for i in range(N):
    rx, ry = rs[i]
    for j, b in enumerate(bs):
        bx, by = b
        if rx < bx and ry < by:
            dinic.add_edge(i, N+j, 1)
for i in range(N):
    dinic.add_edge(2*N, i, 1)
    dinic.add_edge(N+i, 2*N+1, 1)
print(dinic.max_flow(2*N, 2*N+1))

Submission status: Accepted

Solution code:
N = int(input())
Red, Blue = [], []
for i in range(N):
    a, b = map(int, input().split())
    Red.append((a, b))
for i in range(N):
    c, d = map(int,input().split())
    Blue.append((c, d))
Blue.sort()

Ans = 0
for b in Blue:
    temp = (-1, -1)
    for r in Red:
        if r[0] < b[0] and r[1] < b[1]:
            if temp[1] < r[1]:
                temp = r
    if temp != (-1, -1):
        Ans += 1
        Red.remove(temp)
  
print(Ans)

Submission status: Accepted

Solution code:
N = int(input())
rs = [tuple(map(int,input().split())) for i in range(N)]
bs = [tuple(map(int,input().split())) for i in range(N)]

bs.sort()
rs.sort(key=lambda x:-x[1])

removed = [0]*N
ans = 0
for bx,by in bs:
    for ri in range(N):
        if removed[ri]: continue
        rx,ry = rs[ri]
        if rx < bx and ry < by:
            removed[ri] = 1
            ans += 1
            break
print(ans)

Submission status: Accepted

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

R.sort(key=lambda x:x[1],reverse=True)
B.sort()

ANS=0
checked=[0]*N
for x1,y1 in R:
    for i in range(N):
        x2,y2=B[i]
        if x1<x2 and y1<y2 and checked[i]==0:
            ANS+=1
            checked[i]=1
            break

print(ANS)

Submission status: Accepted

Solution code:
#ABC091C
#Input
ab=[]
cd=[]
N=int(input())
for i in range(N):
    ab.append(list(map(int, input().split())))
for i in range(N):
    cd.append(list(map(int, input().split())))
ab.sort(key=lambda x:(-x[1],x[0]))
cd.sort()
#Preparation
ans=0
#Processing
for i in range(N):
    #i番目のBlueに着目する
    bx=cd[i][0]
    by=cd[i][1]
    for j in range(N):
        #j番目のRedに着目する
        rx=ab[j][0]
        ry=ab[j][1]
        #Compare
        if bx>rx and by>ry:
            ans+=1
            #Erase the used red point
            ab[j][0]=200
            ab[j][1]=200
            break
#Output
print(ans)

Submission status: Accepted

Solution code:

# coding: utf-8
import queue

class Dinic:
    """Implementation of Dinic's Alogorithm"""

    def __init__(self, v, inf = 1000000007):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺
        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0;
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    # 増加バスをdfsで探す
    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            # bfsで到達不可
            if self.level[t] < 0 : return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)

if __name__ =="__main__":
    #H,W=map(int,input().split())
    #C=[list(input()) for i in range(H)]
    N=int(input())
    a=[0 for i in range(N)]
    b=[0 for i in range(N)]
    c=[0 for i in range(N)]
    d=[0 for i in range(N)]
    for i in range(N):
        a[i],b[i]=map(int,input().split())
    for i in range(N):
        c[i],d[i]=map(int,input().split())
    Dn=Dinic(2*N+2)
    for i in range(N):
        for j in range(N):
            if a[i]<c[j] and b[i]<d[j]:
                Dn.add_edge(i+1,j+N+1,1)
        Dn.add_edge(0,i+1,1)
        Dn.add_edge(i+N+1,2*N+1,1)
    ans=Dn.max_flow(0,2*N+1)
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N = int(input())
    R = [li_input() for _ in range(N)]
    B = [li_input() for _ in range(N)]

    R.sort(key=lambda x:x[0], reverse=True)

    pair = 0

    ri = 0
    while ri < len(R):
        rx, ry = R[ri]

        bi = 0
        minby, minbi = 10**10, 10**10
        while bi < len(B):
            bx, by = B[bi]

            if rx < bx and ry < by:
                if by < minby:
                    minby = by
                    minbi = bi
            
            bi += 1
            
        if minbi != 10**10:
            pair += 1
            R.pop(ri)
            B.pop(minbi)
        else:
            ri += 1
    
    print(pair)


main()

Submission status: Accepted

Solution code:
n = int(input())

reds =[list(map(int,input().split())) for i in range(n)]
blues = [list(map(int,input().split())) for i in range(n)]
reds.sort(key=lambda x: x[1],reverse=True)
blues = sorted(blues)
count = 0

# print(reds)
# print(blues)

for i in reds:
  for j in blues:
    if i[0] < j[0] and i[1] < j[1]:
      count += 1
      blues.remove(j)
      break
print(count)

Submission status: Accepted

Solution code:
N=int(input())
reds=[]
for i in range(N):
    reds.append(list(map(int,input().split())))
blues=[]
for i in range(N):
    blues.append(list(map(int,input().split())))
    
reds=sorted(reds,key=lambda x:x[0])
blues=sorted(blues,key=lambda x:x[0])

ans=0
tmp=[]
for b in blues:
    while len(reds)>0:
        r=reds[0]
        if b[0] > r[0]:
            tmp.append(reds.pop(0))
        else:
            break
    tmp=sorted(tmp,key=lambda x:x[1],reverse=True)
    for i,t in enumerate(tmp):
        if t[1]<b[1]:
            ans+=1
            tmp.pop(i)
            break
print(ans)

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



cd_cands = {}
for c, d in cd:
    cands = []
    for a, b in ab:
        if a < c and b < d:
            cands.append((a, b))
    cd_cands[(c, d)] = cands

cd = sorted(cd, key = lambda x: x[0])
ab_set = set(ab)
ans = 0
for c, d in cd:
    cands = cd_cands[(c, d)]
    if len(cands) == 0:
        continue
    cands = sorted(cands, key = lambda x: x[1], reverse = True)
    for cand in cands:
        if cand in ab_set:
            ans += 1
            ab_set.remove(cand)
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
R = []
for _ in range(N):
    a, b = map(int, input().split())
    R.append((a, b))
B = []
for _ in range(N):
    c, d = map(int, input().split())
    B.append((c, d))

U = [False for _ in range(N)]
B.sort()

for c, d in B:
    mi = -1
    my = -1
    for i, (a, b) in enumerate(R):
        if not U[i] and a < c and b < d and my < b:
            mi = i
            my = b
    if mi != -1:
        U[mi] = True
print(U.count(True))

Submission status: Accepted

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

from operator import itemgetter
cnt = 0
while True:
    if len(cd) <= 0:
        break
    K = -1
    ab = sorted(ab, key = itemgetter(1))
    cd = sorted(cd, key = itemgetter(0))
    for i in range(len(ab) - 1, -1, -1):
        if ab[i][0] < cd[0][0] and ab[i][1] < cd[0][1]:
            cnt += 1
            del ab[i]
            K = 1
            break
    del cd[0]

print(cnt)

Submission status: Accepted

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

def main():
    n = int(input())
    red_point = [tuple(map(int, input().split())) for _ in range(n)]
    blue_point = [tuple(map(int, input().split())) for _ in range(n)]
    red_point.sort(key=lambda x:(x[1], x[0]), reverse=True)
    blue_point.sort(key=lambda x:(x[0], x[1]))
    ans = 0
    for blue in blue_point:
        bx, by = blue
        for red in red_point:
            rx, ry = red
            if rx < bx and ry < by:
                red_point.remove(red)
                ans += 1
                break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import namedtuple

N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N)]
cd = [tuple(map(int, input().split())) for i in range(N)]

G = [[] for i in range(N * 2 + 2)]

Edge = namedtuple("Edge", ("to", "cap", "rev"))

def add_edge(frm, to, cap):
    G[frm].append(Edge(to, cap, len(G[to])))
    G[to].append(Edge(frm, 0, len(G[frm]) - 1))

# 現在の頂点, 終点, 増加フロー
def dfs(v, t, f):
    if v == t:
        return f
    used[v] = True
    for i, e in enumerate(G[v]):
        if not used[e.to] and e.cap > 0:
            d = dfs(e.to, t, min(f, e.cap))
            if d > 0:
                G[v][i] = Edge(e.to, e.cap - d, e.rev)
                G[e.to][e.rev] = Edge(v, G[e.to][e.rev].cap + d, i)
                return d
    return 0

for i in range(1, N + 1):
    add_edge(0, i, 1)
    add_edge(N + i, N * 2 + 1, 1)

for i in range(1, N + 1):
    a, b = ab[i - 1]
    for j in range(1, N + 1):
        c, d = cd[j - 1]
        if a < c and b < d:
            add_edge(i, N + j, 1)            

flow = 0
while 1:
    used = [False for i in range(N * 2 + 2)]
    f = dfs(0, N * 2 + 1, 114514)
    if f == 0:
        break
    flow += f

print(flow)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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

n = ni()
red = []
blue = []

for _ in range(n):
    red.append(list(li()))
    
for _ in range(n):
    blue.append(list(li()))
    
# 二部グラフの作成
graph = [{} for _ in range(2*n+2)]

for i,r in enumerate(red):
    for j,b in enumerate(blue):
        if r[0]<b[0] and r[1]<b[1]:
            graph[i+1].update({n+j+1: [1, 1]})
            graph[n+j+1].update({i+1: [0, 0]})
            
for i in range(1,n+1):
    graph[0].update({i: [1, 1]})
    graph[i].update({0: [0, 0]})
    
    graph[n+i].update({2*n+1: [1, 1]})
    graph[2*n+1].update({n+i: [0, 0]})
    

# 最大フロー
def dfs(start:int, goal:int, flow:int, visited:list):
    if start == goal:
        return flow
    
    visited[start] = True
    
    for key,value in graph[start].items():
        to = key
        cap, isFwd = value
        
        if not visited[to] and cap > 0:
            d = dfs(to, goal, min(flow, cap),visited)
            
            if d > 0:
                graph[start][to][0] -= d
                graph[to][start][0] += d
                
                return d
            
    return 0

def max_flow(start: int, goal: int):
    INF = float("inf")
    flow = 0
    while True:
        visited = [False]*(2*n+2)
        f = dfs(start,goal,INF,visited)
        
        if f == 0:
            return flow
        flow += f
        
ans = max_flow(0,2*n+1)
print(ans)

Submission status: Accepted

Solution code:
num=int(input())
a_array=[]
b_array=[]
for n in range(2*num):
    elem=[int(n) for n in input().split()]
    if n < num:
        a_array.append(elem)
    else:
        b_array.append(elem)
a_array.sort(key=lambda x:x[1])
a_array.reverse()
b_array.sort(key=lambda x: x[0])
answer=0
for b_x, b_y in b_array:
    for a_x, a_y in a_array:
        if b_x > a_x and b_y > a_y:
            answer=answer+1
            a_array.remove([a_x,a_y])
            break;
print(answer)

Submission status: Accepted

Solution code:
n=int(input())

f=[[0 for i in range(2*n)] for j in range(2*n)]
r=[10000]
b=[]

for k in range(n):
    i,j=map(int,input().split())
    f[i][j]=1
    
for k in range(n):
    i,j=map(int,input().split())
    f[i][j]=2
    
ans=0

for j in f:
    h=0
    for i in j:
        h+=1
        if i==1:
            r.append(h)
            r.sort()
            r.reverse()
        if i==2:
            for k in r:
                if h>=k:
                    ans+=1
                    r.remove(k)
                    break
                
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for i in range(n)]
li = [list(map(int,input().split())) for i in range(n)]
lis.sort(key=lambda x:x[1],reverse=True)
li.sort()
ans = 0
for lisx,lisy in lis:
  for lix,liy in li:
    if lisx < lix and lisy < liy:
      ans +=1
      li.remove([lix,liy])
      break
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)]

ans = 0
red.sort()
blue.sort()
usedred = [0]*n
usedblue = [0]*n
for i, (a, b) in enumerate(blue):
    if not(usedblue): continue
    maxy = -1
    maxj = 0
    for j, (c, d) in enumerate(red):
        if c < a:
            if d < b and d > maxy and not(usedred[j]):
                maxy = d
                maxj = j
        else:
            break
    if maxy >= 0:
        usedblue[i] = 1 
        usedred[maxj] = 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
r = sorted([list(map(int,input().split())) for i in range(N)],key = lambda x: -1*x[1])
b = sorted([list(map(int,input().split())) for i in range(N)])
ans = 0
for xb,yb in b:
    for xr,yr in r:
        if xr <xb and yr<yb:
            r.remove([xr,yr])
            ans+=1
            break
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
# N = 5
# R = [[0, 0],
#      [7, 3],
#      [2, 2],
#      [4, 8],
#      [1, 6]]

# B = [[8, 5], 
#      [6, 9], 
#      [5, 4], 
#      [9, 1],
#      [3, 7]]
N = int(input())
R = []
for i in range(N):
    a, b = map(int, input().split())
    R.append([a, b])
B = []
for i in range(N):
    c, d = map(int, input().split())
    B.append([c, d])
R.sort(key=itemgetter(0))
B.sort(key=itemgetter(0))
# print(R)
# print(B)
res = 0
for r in R[::-1]:
    rx, ry = r[0], r[1]
    flag1 = False
    flag2 = False
    
    for i, b in enumerate(B):
        if b[0] > rx:
            flag1 = True
            break
    
    if flag1:
        B_tmp = B.copy()[i:]
        B_tmp.sort(key=itemgetter(1))
        for ii, b in enumerate(B_tmp):
            if b[1] > ry:
                flag2 = True
                break
        if flag2:
            res += 1
            B.remove(b)
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Aug 21 21:54:34 2018
ABC091D
@author: maezawa
"""

n = int(input())
ab = []
cd = []

for _ in range(n):
    abi = list(map(int, input().split()))
    ab.append(abi)
for _ in range(n):
    cdi = list(map(int, input().split()))
    cd.append(cdi)
    
ab.sort(key=lambda x:(x[0],x[1]), reverse=True)
cd.sort(key=lambda x:(x[1],x[0]))

cnt = 0
for red in ab:
    for i, blue in enumerate(cd):
        if red[0] < blue[0] and red[1] < blue[1]:
            cnt += 1
            cd.pop(i)
            #print(red, blue)
            break

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
RP,BP = [],[]
for i in range(N):
    a,b = map(int,input().split())
    RP.append((a,b))
for i in range(N):
    c,d = map(int,input().split())
    BP.append((c,d))

Ans = 0
# 青い点をx座標で昇順ソートし、順番にみる
BP.sort()
for bp in BP:
    bx,by = bp
    # 赤い点を全探索、条件を満たすペアをリストアップする
    R_yxi = []
    for i in range(len(RP)):
        rx,ry = RP[i]
        if rx < bx and ry < by:
            R_yxi.append((ry,rx,i))
    # 条件を満たすペアが存在する場合、その中でy座標が最大のものとペアにする
    if len(R_yxi) > 0:
        R_yxi.sort(reverse=True)
        rx,ry,i = R_yxi.pop(0)
        RP.pop(i)
        Ans += 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)]

red.sort(key=lambda x: x[1], reverse=True)  # yの大きい順に並べ替え
blue.sort(key=lambda y: y[0])  # xの小さい順に並べ替え

ans = 0

# 貪欲法
# 青をx座標が小さいものから見ていく。
# ペアにできる赤のうち、できるだけ上にあるものを選ぶ
for b in blue:
    for r in red:
        if r[0] < b[0] and r[1] < b[1]:
            red.remove(r)
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
S = []
for i in range(N):
  S.append(list(map(int,input().split())))

T = []
for i in range(N):
  T.append(list(map(int,input().split())))
S.sort(key=itemgetter(1), reverse=True)
S.sort(key=itemgetter(0))
T.sort(key=itemgetter(0))

cnt = 0
for i in range(len(T)):
  jmax = -1
  ymax = -1
  for j in range(len(S)):
    if S[j][0] < T[i][0]:
      if S[j][1] < T[i][1] and ymax < S[j][1]:
        ymax = S[j][1]
        jmax = j
    else:
      break
  if jmax >= 0:
    cnt += 1
    del S[jmax]

print(cnt)

Submission status: Accepted

Solution code:
from copy import copy

N = int(input())

XtoBR = {}
YtoBR = {}
Rnumber = {}
for i in range(N):
    a, b = map(int, input().split())

    Rnumber[i] = (a, b)
    XtoBR[a] = ("R", i)
    YtoBR[b] = ("R", i)

Bnumber = {}
for i in range(N):
    a, b = map(int, input().split())

    Bnumber[i] = (a, b)
    XtoBR[a] = ("B", i)
    YtoBR[b] = ("B", i)

X_list = sorted(list(XtoBR.keys()))

ClearX = {}
clear = set()

ans = 0
for x in reversed(X_list):
    if(XtoBR[x][0] == "B"):
        clear.add(XtoBR[x][1])
    else:
        ClearX[XtoBR[x][1]] = copy(clear)

Y_list = sorted(list(YtoBR.keys()))

clear = set()
for y in reversed(Y_list):
    if(YtoBR[y][0] == "B"):
        clear.add(YtoBR[y][1])
        continue

    n = YtoBR[y][1]
    allclear = clear & ClearX[n]
    # print(clear, ClearX[n], allclear)
    if(len(allclear) == 0):
        continue

    tmp_x = 2 * N + 1
    tmp = 0
    # print(allclear)
    for i in allclear:
        if(Bnumber[i][0] < tmp_x):
            tmp = i
            tmp_x = Bnumber[i][0]

    ans += 1
    clear.remove(tmp)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a={tuple(map(int,input().split())):False for _ in range(n)}
b=sorted([tuple(map(int,input().split())) for _ in range(n)])

ak=sorted(a.keys(),key=lambda x:x[1])[::-1]

for i in b:
  for j in ak:
    if i[0]<j[0] or i[1]<j[1] or a[j]:continue
    else:
      a[j]=True
      break

print(sum(a.values()))

Submission status: Accepted

Solution code:
n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]
C = [[int(i) for i in input().split()] for j in range(n)]


ans = 0
used = [False] * n
A.sort(key=lambda x:x[1], reverse=True)
C.sort()

for c, d in C:
    i = 0
    while i < n and (used[i] or A[i][0] >= c or A[i][1] >= d):
        i += 1
    if i >= n:
        continue
    ans += 1
    used[i] = True

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]
C = [[int(i) for i in input().split()] for j in range(n)]


ans = []

for bits in range(1, 2**4):
    cnt = 0
    used = [False] * n
    A.sort(key=lambda x:x[bits & 1], reverse=bits >> 1 & 1)
    C.sort(key=lambda x:x[bits >> 2 & 1], reverse=bits >> 3 & 1)

    for a, b in A:
        i = 0
        while i < n and (used[i] or a >= C[i][0] or b >= C[i][1]):
            i += 1
        if i >= n:
            continue
        cnt += 1
        used[i] = True
        i += 1
        

    ans.append(cnt)

print(max(ans))

Submission status: Accepted

Solution code:
n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]
C = [[int(i) for i in input().split()] for j in range(n)]


ans = []

for bits in range(1, 2**4):
    cnt = 0
    used = [False] * n
    A.sort(key=lambda x:x[bits & 1], reverse=bits >> 1 & 1)
    C.sort(key=lambda x:x[bits >> 2 & 1], reverse=bits >> 3 & 1)

    for c, d in C:
        i = 0
        while i < n and (used[i] or A[i][0] >= c or A[i][1] >= d):
            i += 1
        if i >= n:
            continue
        cnt += 1
        used[i] = True

    ans.append(cnt)

print(max(ans))

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
import queue
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


class Dinic:
    def __init__(self, v, inf=sys.maxsize):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺
        self.G[from_].append({'to': to, 'cap': cap, 'rev': len(self.G[to])})
        self.G[to].append({'to': from_, 'cap': 0, 'rev': len(self.G[from_])-1})

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    # 増加バスをdfsで探す
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            # bfsで到達不可
            if self.level[t] < 0:
                return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s, t, self.inf)


@mt
def slv(N, AB, CD):
    cd_ = [(i+1, x, y) for i, (x, y) in enumerate(CD)]
    cd_x = sorted(cd_, key=lambda x: x[1])
    cd_x_keys = [x[1] for x in cd_x]
    cd_y = sorted(cd_, key=lambda x: x[2])
    cd_y_keys = [y[2] for y in cd_y]

    d = Dinic(2*N+2)
    for i in range(1, N+1):
        d.add_edge(0, i, 1)
        d.add_edge(i+N, 2*N+1, 1)
    for i, (x, y) in enumerate(AB):
        ix = bisect.bisect_left(cd_x_keys, x)
        iy = bisect.bisect_left(cd_y_keys, y)
        e = set([j for j, x, y in cd_x[ix:]]) & set(
            [j for j, x, y in cd_y[iy:]])
        for j in e:
            d.add_edge(i+1, j+N, 1)

    return d.max_flow(0, 2*N+1)


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N)]
    CD = [read_int_n() for _ in range(N)]

    print(slv(N, AB, CD))


if __name__ == '__main__':
    main()