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 sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n = ni()
    d = []
    for _ in range(2 * n):
        a, b = ns()
        d.append((a, b, _ // n))

    d.sort(key=lambda x: x[2], reverse=True)
    d.sort()
    pool = []
    r, b = 0, 1
    ans = 0
    for a, b, c in d:
        if c == r:
            pool.append(b)
        else:
            tmp = -1
            for pi in pool:
                if pi < b:
                    tmp = max(tmp, pi)
            if tmp != -1:
                ans += 1
                pool.remove(tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, idx=None):
        self.idx = idx
        self.edge = []
        self.level = None
        self.par = None

class Edge():
    def __init__(self, to, cap, rev=None):
        self.to = to
        self.cap = cap
        self.rev = rev

from collections import deque

class BipartiteMatching():
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.inf = 10**18
        self.source = Node()
        self.sink = Node()
        self.lt = [Node(i) for i in range(n)]
        self.rt = [Node(i) for i in range(m)]
        for i in range(n):
            edge = Edge(self.lt[i], 1)
            rev = Edge(self.source, 0)
            edge.rev, rev.rev = rev, edge
            self.source.edge.append(edge)
            self.lt[i].edge.append(rev)
        for i in range(m):
            edge = Edge(self.sink, 1)
            rev = Edge(self.rt[i], 0)
            edge.rev, rev.rev = rev, edge
            self.rt[i].edge.append(edge)
            self.sink.edge.append(rev)

    def add(self, x, y):
        lt = self.lt[x]
        rt = self.rt[y]
        edge = Edge(rt, 1)
        rev = Edge(lt, 0)
        edge.rev, rev.rev = rev, edge
        lt.edge.append(edge)
        rt.edge.append(rev)

    def maximum_matching(self):
        flow = 0
        while True:
            queue = deque([self.source])
            self.source.level = 0
            self.sink.level = None
            for i in range(self.n):
                self.lt[i].level = None
            for i in range(self.m):
                self.rt[i].level = None
            while queue:
                node = queue.popleft()
                for edge in node.edge:
                    to = edge.to
                    if edge.cap and to.level is None:
                        to.level = node.level + 1
                        queue.append(to)
            if self.sink.level is None: break
            stack = [self.source]
            self.source.par = None
            self.sink.par = None
            for i in range(self.n):
                self.lt[i].par = None
            for i in range(self.m):
                self.rt[i].par = None
            while stack:
                node = stack.pop()
                if node is self.sink:
                    break
                for edge in node.edge:
                    to = edge.to
                    if edge.cap and node.level < to.level:
                        to.par = edge.rev
                        stack.append(to)
            node = self.sink
            while node is not self.source:
                node.par.cap = 1
                node.par.rev.cap = 0
                node = node.par.to
            flow += 1
        return flow

N = int(input())
R = [tuple(map(int, input().split())) for _ in range(N)]
B = [tuple(map(int, input().split())) for _ in range(N)]

bip = BipartiteMatching(N, N)

for i in range(N):
    a, b = R[i]
    for j in range(N):
        c, d = B[j]
        if a < c and b < d:
            bip.add(i, j)

print(bip.maximum_matching())

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

R.sort(key=lambda x: (-x[0], -x[1]))
B.sort(key=lambda x: (x[1], x[0]))

ans = 0
for a, b in R:
    for i in range(len(B)):
        if B[i][0] > a and B[i][1] > b:
            ans += 1
            B.pop(i)
            break
print(ans)

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline())

red = []
for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    red.append((a, b))
red.sort(reverse=True, key=lambda x: x[1])

blue = []
for _ in range(N):
    c, d = map(int, sys.stdin.readline().split())
    blue.append((c, d))
blue.sort()

used = set()
for c, d in blue:
    for a, b in red:
        if a < c and b < d and (a, b) not in used:
            used.add((a, b))
            break

print(len(used))

Submission status: Accepted

Solution code:
N = int(input())
ab = []
for i in range(N):
    ab.append(list(map(int,input().split())))
cd = []
for i in range(N):
    cd.append(list(map(int,input().split())))
cd.sort()
#print(ab[2][1])
#print(cd[2][1])
ans = 0
for i in range(N):
    lis = []
    #print(cd[i])
    for j in range(len(ab)):
        #print(cd[i],ab[j])
        #print(ab)
        if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1]:
            #print(cd[i],ab[j])
            lis.append(ab[j])
    #print(lis)
    if len(lis) > 0:
        lis.sort(key=lambda x:x[1])
        lis.reverse()
        ans += 1
        #print(lis)
        ab.remove(lis[0])
        #print(lis[0])
    #print(ab)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
n = int(input())

red = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    red[b].append(a)

blue = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    blue[b].append(a)


ans = 0
can_use = []
for i in range(1, 2*n):
    for x in red[i-1]:
        heapq.heappush(can_use, -x)

    blue[i].sort(reverse=True)
    ret = []
    for b in blue[i]:
        while can_use:
            maxr = -heapq.heappop(can_use)
            if maxr < b:
                ans += 1
                break
            else:
                ret.append(maxr)
    for x in ret:
        heapq.heappush(can_use, -x)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
ab = [None]*n
cd = [None]*n
for i in range(n):
    ab[i] = tuple(map(int, input().split()))
for i in range(n):
    cd[i] = tuple(map(int, input().split()))
import networkx as nx
g = nx.DiGraph()
for i in range(2*n+2):
    g.add_node(i)
s = 2*n
t = 2*n+1
for i in range(n):
    g.add_edge(s,i, capacity=1)
for i in range(n, 2*n):
    g.add_edge(i, t, capacity=1)
for i in range(n):
    for j in range(n, 2*n):
        if ab[i][0]<cd[j-n][0] and ab[i][1]<cd[j-n][1]:
            g.add_edge(i,j, capacity=1)
val = nx.maximum_flow(g, s, t)
print(val[0])

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
C = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
  C[i][0],C[i][1] = C[i][1],C[i][0]
A.sort(key = lambda x:(-x[0],-x[1]))
C.sort(key = lambda x:(x[0],x[1]))
check  = [False]*N
from bisect import *
ans = 0
for x,y in A:
  ind = bisect_right(C,[y,x])
  while ind<N and (check[ind] == True or x>=C[ind][1]):
    ind += 1
  if ind==N:
    continue
  ans += 1
  check[ind]=True
print(ans)

Submission status: Accepted

Solution code:
import heapq, bisect

N = int(input())
h1 = []
h2 = []
lst = []
dic = {}

for _ in range(N):
  a,b = map(int, input().split())
  dic[a] = b
  lst.append(a)
  
lst.sort()

for _ in range(N):
  t = tuple(map(int, input().split()))
  heapq.heappush(h2, t)

j = 0
k = 0
rlt = 0
while h2:
  t = heapq.heappop(h2)
  j = bisect.bisect_left(lst, t[0])
  g = []
  for i in range(k,j):
    heapq.heappush(h1, -dic[lst[i]])
  while h1:
    c = heapq.heappop(h1)
    if -c < t[1]:
      rlt += 1
      break
    else:
      g.append(c)
  for c in g:
    heapq.heappush(h1, c)
  k = j
  
print(rlt)

Submission status: Accepted

Solution code:
from operator import itemgetter
from bisect import bisect
n = int(input())
a = [tuple(map(int,input().split())) for i in range(n)]
b = [tuple(map(int,input().split())) for i in range(n)]
a.sort(key=itemgetter(1))
a.sort(key=itemgetter(0))
b.sort(key=itemgetter(1))
b.sort(key=itemgetter(0))

ans = 0
for l,r in b:
  ind = bisect(a,(l-1,r-1))
  chk = 0
  d = -1
  for i in range(min(len(a),ind)):
    if a[i][1] < r:
      chk = max(chk,a[i][1])
      if chk == a[i][1]:
        d = i
  if d >= 0:
    ans += 1
    k = a[d]
    a.remove(k)
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
zahyo = [[0 for i in range(2*n)] for j in range(2*n)]
for i in range(n):
    a , b = map(int,input().split())
    zahyo[a][b] = 1

for i in range(n):
    c , d = map(int,input().split())
    zahyo[c][d] = -1
ans = 0
for i in range(2*n):#x R
    for j in range(2*n):#y R
        if zahyo[i][j] == -1:
            flag = False
            for l in reversed(range(j)):#y B
                if flag:
                    break
                for k in reversed(range(i)):#x B
                    if zahyo[k][l] == 1:
                        zahyo[i][j] = 0
                        zahyo[k][l] = 0
                        flag = True
                        ans += 1
                        break
print(ans)

Submission status: Accepted

Solution code:
# 青の点をX座標が小さい順に見ていく
# それよりX座標が小さい赤の点で、最もY座標が大きいものとペアにする
# N = 100なので3重ループ回す

import sys
readline = sys.stdin.readline

N = int(readline())

R = [None] * N
B = [None] * N
for i in range(N):
  x,y = map(int,readline().split())
  R[i] = (x,y)
  
for i in range(N):
  x,y = map(int,readline().split())
  B[i] = (x,y)
  
R = sorted(R, key = lambda x:x[0])
B = sorted(B, key = lambda x:x[0])

ans = 0
used = set()
for b in B:
  bx,by = b
  max_ry = -1
  max_ind = -1
  for i in range(len(R)):
    rx,ry = R[i]
    if (rx,ry) in used:
      continue
    if ry >= by:
      continue
    if rx >= bx:
      break
    if ry > max_ry:
      max_ry = ry
      max_ind = i
  if max_ind != -1:
    ans += 1
    used.add(R[max_ind])
      
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import bisect

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
	N = NI()
	R = [NLI() for _ in range(N)]
	B = [NLI() for _ in range(N)]
	R.sort(key= lambda x: x[1], reverse=True)
	B.sort(key= lambda x: x[0])
	ans = 0

	for b in B:
		for r in R:
			if r[0] < b[0] and r[1] < b[1]:
				ans += 1
				R.remove(r)
				break
	
	print(ans)





if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, insort_left
n = int(input())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
cd = []
for _ in range(n):
    c, d = map(int, input().split())
    cd.append((c, d))
ab.sort()
cd.sort()
ans = 0
q = []
ind = 0
for i in range(n):
    for j in range(ind, n):
        if ab[j][0]>cd[i][0]:
            ind = j
            break
        insort_left(q, ab[j][1])
    else:
        ind = n
    tmp = bisect_left(q, cd[i][1])
    if tmp>0:
        q.pop(tmp-1)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# Dinic's algorithm
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

n = int(input())
rl = [list(map(int, input().split())) for _ in range(n)]
bl = [list(map(int, input().split())) for _ in range(n)]

dinic = Dinic(2*n+10)
s = 2*n
e = 2*n + 1
for i in range(n):
    dinic.add_edge(s,i,1)
    dinic.add_edge(n+i,e,1)

for i in range(n):
    for j in range(n):
        r = rl[i]
        b = bl[j]
        if r[0]<b[0] and r[1]<b[1]:
            dinic.add_edge(i,n+j,1)

print(dinic.flow(s,e))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc092/submissions/13926597
# 最大流で解くという発想

# https://tjkendev.github.io/procon-library/python/max_flow/dinic.html


# Dinic's algorithm
from collections import deque


class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None] * self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10 ** 9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


def main():
    N = int(input())

    reds = [tuple(map(int, input().split())) for _ in range(N)]
    blues = [tuple(map(int, input().split())) for _ in range(N)]

    dnc = Dinic(N * 2 + 2)
    for i, (rx, ry) in enumerate(reds, start=1):
        dnc.add_edge(fr=0, to=i, cap=1)
        for j, (bx, by) in enumerate(blues, start=N + 1):
            if rx < bx and ry < by:
                dnc.add_edge(fr=i, to=j, cap=1)

    for j in range(N + 1, N * 2 + 1):
        dnc.add_edge(fr=j, to=N * 2 + 1, cap=1)

    ans = dnc.flow(0, N * 2 + 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc092/submissions/13926597
# 最大流で解くという発想

# https://tjkendev.github.io/procon-library/python/max_flow/ford-fulkerson.html


# Ford-Fulkerson algorithm
class FordFulkerson:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def dfs(self, v, t, f):
        if v == t:
            return f
        used = self.used
        used[v] = 1
        for e in self.G[v]:
            w, cap, rev = e
            if cap and not used[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        f = INF = 10 ** 9 + 7
        N = self.N
        while f:
            self.used = [0] * N
            f = self.dfs(s, t, INF)
            flow += f
        return flow


def main():
    N = int(input())

    reds = [tuple(map(int, input().split())) for _ in range(N)]
    blues = [tuple(map(int, input().split())) for _ in range(N)]

    ff = FordFulkerson(N * 2 + 2)
    for i, (rx, ry) in enumerate(reds, start=1):
        ff.add_edge(fr=0, to=i, cap=1)
        for j, (bx, by) in enumerate(blues, start=N + 1):
            if rx < bx and ry < by:
                ff.add_edge(fr=i, to=j, cap=1)

    for j in range(N + 1, N * 2 + 1):
        ff.add_edge(fr=j, to=N * 2 + 1, cap=1)

    ans = ff.flow(0, N * 2 + 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
red = []
blue = []

for _ in range(n):
    a,b = map(int,input().split())
    red.append((a,b))

for _ in range(n):
    c,d = map(int,input().split())
    blue.append((c,d))

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

bk = [True]*n
rk = [True]*n
point = 0

for i in range(n):
    for j in range(n):
        if blue[i][0] > red[j][0] and blue[i][1] > red[j][1]:
            if bk[i] and rk[j]:
                point += 1
                bk[i] = False
                rk[j] = False

print(point)

Submission status: Accepted

Solution code:
# editorial

def main():
    from operator import itemgetter

    N = int(input())
    reds = [tuple(map(int, input().split())) for _ in range(N)]
    blues = [tuple(map(int, input().split())) for _ in range(N)]

    reds.sort(key=itemgetter(0))
    blues.sort(key=itemgetter(0))

    used = [0] * N
    for bx, by in blues:
        mai = -1
        may = -1
        for i, (is_used, (rx, ry)) in enumerate(zip(used, reds)):
            if is_used: continue
            if rx >= bx: break
            if (ry >= by) or (~mai and may >= ry): continue
            mai = i
            may = ry
        if ~mai:
            used[mai] = 1

    print(sum(used))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
ab = [inpl() for _ in range(n)]
cd = [inpl() for _ in range(n)]
ab.sort(key = lambda x:x[1],reverse = True)
cd.sort()
seen = [False] * n
for j in range(n):
    c,d = cd[j]
    for i,(a,b) in enumerate(ab):
        if seen[i]: continue
        if a < c and b < d:
            seen[i] = True
            break
print(sum(seen))

Submission status: Accepted

Solution code:
N = int(input())
red = []
for _ in range(N):
    a,b = map(int,input().split())
    red.append(tuple([a,b]))

blue = []
for _ in range(N):
    a,b = map(int,input().split())
    blue.append(tuple([a,b]))

red.sort(reverse=True)
blue.sort()

t = None
cnt = 0
for i in range(N):
    rx = red[i][0]
    ry = red[i][1]
    for j in range(len(blue)):
        bx = blue[j][0]
        if rx < bx:
            miny = 201
            for b in blue[j:]:
                if ry < b[1]:
                    if miny > b[1]:
                        miny = b[1]
                        t =b
            break
    # print(red[i],t)

    if t != None:
        # print(red[i],t)
        blue.remove(t)
        cnt += 1
    t = None

print(cnt)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    AB = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0],
                reverse=True)
    CD = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[1])

    res = 0
    for i in range(n):
        a, b = AB[i]
        for j in range(len(CD)):
            c, d = CD[j]
            if a < c and b < d:
                res += 1
                CD.pop(j)
                break

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

N = int(input())

AB = [tuple(map(int, input().split())) for _ in range(N)]
CD = [tuple(map(int, input().split())) for _ in range(N)]

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

def dfs(v, t, f):
    if v == t:
        return f
    used[v] = True
    for i in range(len(G[v])):
        e = G[v][i]
        if (not used[e[0]]) and e[1] > 0: #辺が使われていなくてかつ残量が0より多い
            d = dfs(e[0], t, min(f, e[1]))
            if d > 0: #更新できるとき
                e[1] -= d
                G[e[0]][e[2]][1] += d
                return d
    return 0

def max_flow(s, f):
    flow = 0
    while True:
        global used
        used = [False] * (2 * N + 2)
        t = dfs(s, f, INF)
        if t == 0:
            return flow
        flow += t

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

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

for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            add_edge(i, j + N, 1)
 
print (max_flow(2 * N, 2 * N + 1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
from collections import *

class FordFulkerson:
    def __init__(self, N, edges):
        self.N = N
        self.G = defaultdict(lambda : defaultdict(int))
        
        for s, t, cap in edges:
            self.G[s][t] = cap
        
    def dfs(self, v, t, f):
        if v==t:
            return f
        
        self.used[v] = True
        
        for nv, cap in self.G[v].items():
            if not self.used[nv] and self.G[v][nv]>0:
                d = self.dfs(nv, t, min(f, self.G[v][nv]))
                
                if d>0:
                    self.G[v][nv] -= d
                    self.G[nv][v] += d
                    
                    return d
        
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        
        while True:
            self.used = [False]*self.N
            f = self.dfs(s, t, 10**18)
        
            if f==0:
                return flow
        
            flow += f

N = int(input())
edges = []

for i in range(1, N+1):
    edges.append((0, i, 1))

for i in range(N+1, 2*N+1):
    edges.append((i, 2*N+1, 1))

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

for i in range(N):
    for j in range(N):
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
            edges.append((1+i, N+1+j, 1))

ff = FordFulkerson(2*N+2, edges)
print(ff.max_flow(0, 2*N+1))

Submission status: Accepted

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

P = 2*N+2
es = [[] for i in range(P)] # [[to1,cap1,rev1], ...]

def add_edge(fr,to,cap):
    es[fr].append([to,cap,len(es[to])])
    es[to].append([fr,0,len(es[fr])-1])

for i in range(N):
    add_edge(2*N,i,1)
    add_edge(N+i,2*N+1,1)
for i,(a,b) in enumerate(AB):
    for j,(c,d) in enumerate(CD):
        if a<c and b<d:
            add_edge(i,j+N,1)

INF = float('inf')
level = [0] * P
iters = [0] * P
from collections import deque
def dinic_max_flow(s,t):
    global iters

    def _bfs(s):
        global level
        level = [-1] * P
        level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for to,cap,rev in es[v]:
                if cap > 0 and level[to] < 0:
                    level[to] = level[v] + 1
                    q.append(to)

    def _dfs(v,t,f):
        if v == t: return f
        for i in range(iters[v],len(es[v])):
            iters[v] += 1
            to,cap,rev = es[v][i]
            if es[v][i][1] > 0 and level[v] < level[to]:
                d = _dfs(to,t,min(f,es[v][i][1]))
                if d > 0:
                    es[v][i][1] -= d #cap
                    es[to][rev][1] += d
                    return d
        return 0

    flow = 0
    while True:
        _bfs(s)
        if level[t] < 0: return flow
        iters = [0] * P
        f = 0
        while True:
            f = _dfs(s,t,INF)
            if f <= 0: break
            flow += f

print(dinic_max_flow(2*N,2*N+1))

Submission status: Accepted

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


class BipartiteMatching:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.pairA = [-1] * N
        self.pairB = [-1] * M
        self.edge = [[] for _ in range(N)]
        self.was = [0] * N
        self.iter = 0

    def add(self, s, t):
        self.edge[s].append(t)

    def _DFS(self, s):
        self.was[s] = self.iter
        for t in self.edge[s]:
            if self.pairB[t] == -1:
                self.pairA[s] = t
                self.pairB[t] = s
                return True
        for t in self.edge[s]:
            if self.was[self.pairB[t]] != self.iter and self._DFS(self.pairB[t]):
                self.pairA[s] = t
                self.pairB[t] = s
                return True
        return False

    def solve(self):
        res = 0
        while True:
            self.iter += 1
            found = 0
            for i in range(self.N):
                if self.pairA[i] == -1 and self._DFS(i):
                    found += 1
            if not found:
                break
            res += found
        return res


if __name__ == "__main__":
    N = int(input())
    AB = tuple(tuple(map(int, input().split())) for _ in range(N))
    CD = tuple(tuple(map(int, input().split())) for _ in range(N))
    match = BipartiteMatching(N + 5, N + 5)

    for i, (a, b) in enumerate(AB):
        for j, (c, d) in enumerate(CD):
            if a < c and b < d:
                match.add(i, j)
    print(match.solve())

Submission status: Accepted

Solution code:
import bisect as bs
import sys

n = int(input())
array = []

for i in range(n):
  a,b = map(int, input().split())
  array.append((a,b,False))
  
for j in range(n):
  c,d = map(int, input().split())
  array.append((c,d,True))
  
array.sort()

blue = []

count = 0 
for v in array:
  if v[2]:
    index = bs.bisect_left(blue, v[1])
    if index != 0:
      blue[index-1] = sys.maxsize
      count += 1
      blue.sort()
      
  else:
    blue.append(v[1])
    blue.sort()
    
print(count)

Submission status: Accepted

Solution code:
N=int(input())

red=[]
blue=[]
counter=0

for _ in range(N):
    red.append(list(map(int,(input().split()))))

for _ in range(N):
    blue.append(list(map(int,(input().split()))))

blue.sort()

for i in blue:
    a=i[0]
    b=i[1]

    taisho=[j for j in red if j[0]<a]
    
    if len(taisho)>=1:
        taisho.sort(key=lambda x:x[1],reverse=True)
        for k in taisho:
            if k[1]<b:
                counter+=1
                red.remove(k)
                break

print(counter)

Submission status: Accepted

Solution code:
n = int(input())
k1 = [None]*(2*n)
for i in range(n):
  a, b = map(int, input().split())
  k1[i] = (a, b, 0)
for j in range(n, 2*n):
  c, d = map(int, input().split())
  k1[j] = (c, d, 1)
k1.sort()
key = []
ans = 0
for i in range(2*n):
  a, b, c = k1[i][0], k1[i][1], k1[i][2]
  if c == 0:
    key.append(b)
    key.sort()
    continue
  for j in range(len(key)-1, -1, -1):
    if key[j] < b:
      ans += 1
      key.remove(key[j])
      break
print(ans)

Submission status: Accepted

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

B.sort()
ans=0
chk=[0 for _ in range(N)]
for c,d,num in B:
    l=[]
    for a,b,r in R:
        if chk[r]==1:
            continue
        if a<c and b<d:
            l.append([b,r])
    if len(l)==0:
        continue
    l.sort(reverse=True)
    chk[l[0][1]]=1
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**3
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
red = [LI() for _ in range(N)]
blue = [LI() for _ in range(N)]
red.sort(key=lambda x:x[1],reverse=True)
blue.sort()

ans = 0
for bx,by in blue:
    for i in range(N):
        if bx > red[i][0] and by > red[i][1]:
            ans += 1
            red[i][0] = INF
            break
print(ans)