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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  lr = sorted([list(map(int, input().split())) for _ in range(n)])
  lb = sorted([list(map(int, input().split())) for _ in range(n)])
  
  cnt = 0
  for b in lb:
    cands = sorted([r for r in lr if r[0] < b[0] and r[1] < b[1]], key = lambda x:x[1])
    if len(cands) == 0:
      continue
    cnt += 1
    lr.remove(cands[-1])
  print(cnt)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import queue
class Dinic:
    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(input())
red=[list(map(int,input().split())) for i in range(n)]
blue=[list(map(int,input().split())) for i in range(n)]

dinic = Dinic(2600)

for i in range(n):
    bx,by = blue[i]
    for j in range(n):
        rx,ry = red[j]
        if rx<bx and ry<by:
            dinic.add_edge(i,j+1000,1)

for i in range(n):
    dinic.add_edge(2000,i,1)
    dinic.add_edge(i+1000,2500,1)

print(dinic.max_flow(2000,2500))

Submission status: Accepted

Solution code:
# 赤：X軸降順でソート
# 青：Y軸昇順でソート
# 青を順に処理して、条件を満たす赤があれば採用する
N = int(input())

red = [None] * N
for i in range(N):
  red[i] = tuple(map(int,input().split()))

red = sorted(red, key = lambda x:-x[0])

blue = [None] * N
for i in range(N):
  blue[i] = tuple(map(int,input().split()))

blue = sorted(blue, key = lambda x:x[1])

ans = 0
for b in blue:
  found = -1
  for i in range(len(red)):
    if red[i][0] < b[0] and red[i][1] < b[1]:
      ans += 1
      found = i
      break
  if found != -1:
    del red[found]

print(ans)

Submission status: Accepted

Solution code:
# 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

N=int(input())

red_list=[]
for i in range(N):
  a,b=map(int,input().split())
  red_list.append((a,b,N+i+1))
  
blue_list=[]
for i in range(N):
  c,d=map(int,input().split())
  blue_list.append((c,d,i+1))
    
#print(blue_list)
#print(red_list)

#[s=0]->[blue:1..N]->[red:N+1..2N]->[t=2N+1]
ff = FordFulkerson(2*N+2)
for i in range(N):
  #print(0,i+1)
  ff.add_edge(0,i+1,1)
for c,d,ind1 in blue_list:
  for a,b,ind2 in red_list:
    if a<c and b<d:
      #print(ind1,ind2)
      ff.add_edge(ind1,ind2,1)  
for i in range(N):
  #print(N+i+1,2*N+1)
  ff.add_edge(N+i+1,2*N+1,1)

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

Submission status: Accepted

Solution code:
#!python3

INF = 10 ** 15


# input
N = int(input())
a, b, c, d = [None] * N, [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i] = list(map(int, input().split()))
for i in range(N):
    c[i], d[i] = list(map(int, input().split()))


class MaxFlow():

    def __init__(self, n):
        self.n = n
        self.c = [[0] * n for _ in range(n)]
        self.visit = [False] * n

    def add_link(self, x, y, capa):
        self.c[x][y] += capa
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        self.visit[v] = True
        
        for i in range(self.n):
            if self.visit[i] or self.c[v][i] == 0:
                continue
            d = self.dfs(i, t, min(f, self.c[v][i]))
            if d > 0:
                self.c[v][i] -= d
                self.c[i][v] += d
                return d
                
        return 0

    
    def max_flow(self, s, t):
        ans = 0
        while True:
            f = self.dfs(s, t, INF)
            self.visit = [False] * self.n
            if f == 0:
                return ans
            else:
                ans += f
        

def main():
    w = MaxFlow(2 * N + 2)
    for i in range(N):
        w.add_link(0, i + 1, 1)
        w.add_link(N + i + 1, 2 * N + 1, 1)
        for j in range(N):
            if a[i] < c[j] and b[i] < d[j]:
                w.add_link(i + 1, N + j + 1, 1)
    
    ans = w.max_flow(0, 2 * N + 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#2d plane 2n points
n=int(input())
cnt=0
red=[]
blue=[]
for _ in range(n):
    x,y=map(int,input().split())
    red.append((x,y))
for _ in range(n):
    x,y=map(int,input().split())
    blue.append((x,y))
red=sorted(red,key=lambda x:x[0])
blue=sorted(blue,key=lambda x:x[0])
blue=blue[::-1]
for i in range(n-1,-1,-1):
    x,y=red[i][0],red[i][1]
    d=[]
    for some in blue:
        X,Y=some[0],some[1]
        if X>x:
            d.append((X,Y))
    if d:
        d=sorted(d,key=lambda x:x[1])
        node=0
        for some in d:
            if some[1]>y:
                node=some
                cnt+=1
                break
        if node!=0:
            blue.remove(node)
print(cnt)

Submission status: Accepted

Solution code:
ab=[]
cd=[]
n=int(input())
for i in range(n):
	a,b=map(int,input().split())
	ab.append([a,b])
for i in range(n):
	c,d=map(int,input().split())
	cd.append((c,d))
ab.sort()
cd.sort()
ans=0
for i in range(n):
	p=-1
	erase=-1
	for j in range(n):
		if cd[i][0]>ab[j][0]:
			if p<=ab[j][1] and ab[j][1]<cd[i][1]:
				p=ab[j][1]
				erase=j
		elif ab[j]!=(1000,1000):
			break
	if p!=-1:
		ans+=1
		ab[erase]=(1000,1000)
print(ans)

Submission status: Accepted

Solution code:
#ARC092-C 2D Plane 2N Points
"""
重みなし2部マッチング問題
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#ネットワークフロー
#最大流,最小カット
import queue
class Dinic():
    #Dinic法,O(|E||V|**2) ※但し、実際にはもっと高速な動作

    def __init__(self, v, inf = 10**10):
        # v:頂点数
        # G:辺情報.各頂点に対し、[行き先,重み,(この辺を含めず)既に存在する行き先の辺数]
        # level:startからの距離(これはcapacityを考慮しない) bfsで毎回リセットされる
        # iter:各頂点について、どこまで調べ終わったかを記録する
        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: 反対側の辺

        # 無向グラフの場合、G[to]の方のcapを0→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']]: #流れているかつ、levelが大きいなら
                d = self.dfs(e['to'], t, min(f, e['cap'])) # d:流量
                if d > 0:
                    e['cap'] -= d #使用済みの分だけcapから引く
                    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) #levelの更新
            # bfsでtに到達不可なら終了
            if self.level[t] < 0 : return flow
            #イテレータの初期化(イテレータ：各頂点に対し、どこまで調べ終わったか)
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf) #f:そのパスの流量
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)

n = int(readline())
red = []
blue = []
for i in range(n):
    x,y = map(int,readline().split())
    red.append([x,y])
for i in range(n):
    x,y = map(int,readline().split())
    blue.append([x,y])

N = 2*n
network = Dinic(N+2) #source=0,sink=n+1
source = 0
sink = N+1

red.sort()
blue.sort()

for b,i in enumerate(blue,1):
    for r,j in enumerate(red,1):
        if i[0] > j[0] and i[1] > j[1]:
            network.add_edge(b,n+r,1)
        elif i[0] <= j[0]:
            break

for i in range(1,n+1):
    network.add_edge(source,i,1)
    network.add_edge(n+i,sink,1)

print(network.max_flow(source,sink))

Submission status: Accepted

Solution code:
# 解説参照
# 安易なソート順の貪欲ではだめ
# x最小青と組める赤のうちy最大
# どうやって気づくのかは知らない

n = int(input())
#赤
p1 = [tuple(map(int, input().split( ))) for i in range(n)]
#青
p2 = [tuple(map(int, input().split( ))) for i in range(n)]
p2.sort()
#赤＜青

used = [0]*(n+1) 
ans = 0

for j in range(n):
    y = -1
    ind = -1
    for i in range(n):
        if p1[i][0]<p2[j][0] and p1[i][1]<p2[j][1] and not used[i]:
            if y<p1[i][1]:
                y = p1[i][1]
                ind = i
    if ind>=0:
        ans += 1
        used[ind] = 1
        
print(ans)

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 = [list(map(int, input().split())) for _ in range(N)]
    CD = [list(map(int, input().split())) for _ in range(N)]

    match = BipartiteMatching(N, N)

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


def inv(a, mod):
    return pow(a, mod - 2, mod)


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N = int(input())
    R = [tuple(read_values()) for _ in range(N)]
    B = [tuple(read_values()) for _ in range(N)]
    B.sort()
    res = 0
    paired = [False] * N
    for bx, by in B:
        t = -1
        for i, (rx, ry) in enumerate(R):
            if paired[i]:
                continue

            if rx < bx and ry < by:
                if t == -1 or R[t][1] < ry:
                    t = i

        if t != -1:
            res += 1
            paired[t] = True
    print(res)


if __name__ == "__main__":
    main()

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=sorted(ab,key=lambda x:x[1],reverse=True)
cd=sorted(cd)
for c,d in cd:
    for a,b in ab:
        if a<c and b<d:
            ab.remove((a,b))
            break
print(n-len(ab))

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
ab = []
cd = []
for i in range(n):
    ab.append(tuple(inl()))
for i in range(n):
    cd.append(tuple(inl()))
ab.sort()
cd.sort()
usedcd = [0]*n
while len(ab)>0:
    a,b = ab.pop()
    mn = BIG
    for i in range(n-1,-1,-1):
        if a>=cd[i][0]:
            break
        if usedcd[i]==0 and b<cd[i][1]<mn:
           mn = cd[i][1]
           mni = i
    if mn<BIG:
        usedcd[mni] = 1
print(sum(usedcd))

Submission status: Accepted

Solution code:
n=int(input())
r=sorted([list(map(int,input().split()))for i in range(n)], key=lambda r: -r[1])
b=sorted([list(map(int,input().split()))for i in range(n)])
ans=0
for c,d in b:
  for a,x in r:
    if a<c and x<d:
      r.remove([a,x])
      ans+=1
      break
print(ans)

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], reverse=True)
BLUE.sort(key=lambda x:x[0])

ans=0
r_used=[False]*N
for b in BLUE:
    for j,r in enumerate(RED):
        if r_used[j]: continue
        if r[0]<b[0] and r[1]<b[1]:
            ans+=1
            r_used[j]=True
            break
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 

n = int(readline())

red = []
for i in range(n):
    a,b = map(int,readline().split())
    red.append([a,b])

blue = []
for i in range(n):
    a,b = map(int,readline().split())
    blue.append([a,b])

red.sort(reverse=True,key=itemgetter(1))
blue.sort()

ans = 0
used = []
for c,d in blue:
    for a,b in red:
        if c > a and d > b:
            if not (a,b) in used:
                ans += 1
                used.append((a,b))
                break

print(ans)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math

N=int(input())
AB=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0])
CD=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0])
count=0
for c,d in CD:
    #print(AB,c,d)
    tmp=[[AB[i][1],i] for i in range(len(AB)) if AB[i][0]<c and AB[i][1]<d]
    if tmp:
        idx=tmp[0][1]
        _max=tmp[0][0]
        for a,i in tmp:
            if a>_max:

                _max=a
                idx=i

        AB.pop(idx)
        count+=1
print(count)

Submission status: Accepted

Solution code:
N=int(input())

red=[]
for _ in range(N):
    a,b=map(int,input().split())
    red.append([a,b])
red.sort(key=lambda x:x[1])
red.sort(key=lambda x:x[0])

blue=[]
for _ in range(N):
    c,d=map(int,input().split())
    blue.append([c,d])
blue.sort(key=lambda x:x[1])
blue.sort(key=lambda x:x[0])


ans=0
for i in range(N):
    mx,log=0,-1
    for j in range(N):
        #print(i,blue[i],red[j])
        if blue[i][0]<=red[j][0]:
            continue                    
        if blue[i][1]>red[j][1]:
            mx=max(red[j][1],mx)
            if mx==red[j][1]:
                log=j
    if log!=-1:
        red[log]=[10**9,10**9]
        ans+=1        
        


#print(red)
#print(blue)
print(ans)

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.sort(reverse=True)

ans  = 0
used = set([-1])

for x, y in R:
    take = -1
    for i, (u, v) in enumerate(B):
        if x < u and y < v and (not i in used):
            if take == -1:
                take = i
            else:
                if v < B[take][1]:
                    take = i
    if not take in used:
        ans += 1
        used.add(take)

print(ans)

Submission status: Accepted

Solution code:
def findPath(x):
    if x==(200,200,2):
        for i in range(len(A)-1):
            G[A[i]].remove(A[i+1])
            G[A[i+1]].append(A[i])
        return True
    for y in G[x]:
        if hist[(x[0],x[1],y[0],y[1])]==0:
            hist[(x[0],x[1],y[0],y[1])]=1
            A.append(y)
            if findPath(y):
                return True
            A.pop()
    return False
N = int(input())
G = {}
for _ in range(N):
    a,b = map(int,input().split())
    G[(a,b,0)] = []
G[(-1,-1,-1)] = []
for x in G:
    if x[2]==0:
        G[(-1,-1,-1)].append(x)
for _ in range(N):
    c,d = map(int,input().split())
    G[(c,d,1)] = [(200,200,2)]
    for x in G:
        a,b,s = x[0],x[1],x[2]
        if s==0 and a<c and b<d:
            G[(a,b,0)].append((c,d,1))
G[(200,200,2)] = []
F = 0    
while True:
    A = [(-1,-1,-1)]
    hist = {(a,b,c,d):0 for (a,b,s1) in G for (c,d,s2) in G[(a,b,s1)]}
    if findPath((-1,-1,-1)):
        F += 1
    else:break
print(F)

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
ab = sorted([ list(map(int, input().split())) for _ in range(n) ], key=itemgetter(1), reverse=True)
cd = sorted([ list(map(int, input().split())) for _ in range(n) ])
ans = 0
sab = []
for i in range(n):
  for j in range(n):
    if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1]:
      if ab[j] not in sab:
        ans += 1
        sab.append(ab[j])
        break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
CD = [list(map(int, input().split())) for _ in range(N)]

CD.sort()
red_check = [0] * N

for i in range(N):
  c, d = CD[i]
  bmax = - 10 ** 15
  maxj = -1
  for j in range(N):
    if red_check[j] == 0:
      a, b = AB[j]
      if a < c and b < d and b > bmax:
        bmax = b
        maxj = j
  if maxj != -1:
    red_check[maxj] = 1

print(sum(red_check))

Submission status: Accepted

Solution code:
def main():

  n=int(input())
  ab=[] #red
  for i in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
  ab.sort(reverse=True,key=lambda x:x[1])

  cd=[] #blue
  for i in range(n):
    c,d=map(int,input().split())
    cd.append((c,d))
  cd.sort(reverse=False,key=lambda x:x[0])

  cnt=0
  checked_cd=[]
  checked_ab=[]
  for i,(c,d) in enumerate(cd):
    for j,(a,b) in enumerate(ab):
      if i in checked_cd or j in checked_ab:
        continue

      if a<c and b<d:
        cnt+=1
        checked_cd.append(i)
        checked_ab.append(j)

  print(cnt)
  
main()

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)]
ab.sort()
cd.sort()
usedb = [0]*(n+1)
usedr = [0]*(n+1)
ymax = -1
ans = 0
for q,[c,d] in enumerate(cd):
    for p,[a,b] in enumerate(ab):
        if c>a and d>b and usedb[q] == 0 and usedr[p] == 0:
            if b>ymax:
                ymax = b
                r = p
    if ymax >= 0:
        usedr[r] = 1
        usedb[q] = 1
        ans += 1
    ymax = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ in range(2*N+2)] #残余グラフを構成　0を始点，1を終点とする

for i in range(N):
    forward = [2+i,1,None] #[行き先，流量，逆辺の情報]
    forward[2] = backward = [0,0,forward]
    graph[0].append(forward)
    graph[2+i].append(backward)

for i in range(N):
    forward = [1,1,None]
    forward[2] = backward = [2+N+i,0,forward]
    graph[2+N+i].append(forward)
    graph[1].append(backward)

for i in range(N):
    for j in range(N):
        if R[i][0]<B[j][0] and R[i][1]<B[j][1]:
            forward = [2+N+j,1,None]
            forward[2] = backward = [2+i,0,forward]
            graph[2+i].append(forward)
            graph[2+N+j].append(backward)

flow = 0
while True:

    queue = deque([0])
    level = [None for _ in range(2*N+2)]
    level[0] = 0

    while queue:
        node = queue.popleft()
        for adj,adjcap,_ in graph[node]:
            if adjcap>0 and level[adj] is None:
                level[adj] = level[node]+1
                queue.append(adj)

    if level[1] is None:
        break

    stack = [0]
    visited = [0 for _ in range(2*N+2)]
    visited[0] = 1
    parent = [None for _ in range(2*N+2)]
    parent[0] = 0
    #*it, = map(iter, graph)
    
    while stack:
        node = stack.pop()
        for adj,adjcap,adjrev in graph[node]:
            if not visited[adj] and adjcap>0 and level[node]<level[adj]:
                visited[adj] = 1
                parent[adj] = node
                stack.append(adj)
                
    if visited[1]:
        flow += 1
        node = 1
        prev = parent[node]
        while node != 0:
            for g in graph[prev]:
                adj,adjcap,adjrev = g
                if adj == node:
                    g[1] = 0
                    adjrev[1] = 1
            node = prev
            prev = parent[node]
            
print(flow)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
R=[]
B=[]

for i in range(n):
    a,b=LI()
    R.append((a,b))

for i in range(n):
    a,b=LI()
    B.append((a,b))

RR=[]
B.sort(key=lambda x:x[0])
R.sort(key=lambda x:-x[0])
ans=0

for c,d in B:
    while R and R[-1][0]<c:
        RR.append(R.pop())
    
    RR.sort(key=lambda x:-x[1])
    for a,b in RR:
        if a<c and b<d:
            ans+=1
            RR.remove((a,b))
            break
        
print(ans)

#show(d)

Submission status: Accepted

Solution code:
N=int(input())
r=[]
for i in range(N):
    r.append(tuple(map(int,input().split())))
r.sort(key=lambda x:x[1]) # y座標で昇順ソート
b=[]
for i in range(N):
    b.append(tuple(map(int,input().split())))
b.sort() # x座標で昇順ソート

# print(r)
# print(b)

ans=0
for bi in b:
    # print(bi)
    rs=[ri for ri in r if ri[0]<bi[0] and ri[1]<bi[1]]
    # print(rs)
    if rs:
        ans+=1
        r.remove(rs[-1])
    # print(r)

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())
D = Dinic(N*2+2)
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))
for i in range(N):
    D.add_edge(0, i+1, 1)
    D.add_edge(i+1+N, N*2+1, 1)
    for j in range(N):
        a, b = red[i]
        c, d = blue[j]
        if a<c and b<d:
            D.add_edge(i+1, j+1+N, 1)
print(D.flow(0, N*2+1))

Submission status: Accepted

Solution code:
N=int(input())
Red=[[int(s) for s in input().split()] for _ in range(N)]
Blue=[[int(s) for s in input().split()] for _ in range(N)]

#x座標が小さい順->y座標が大きい順にソート
Blue=sorted(Blue,key=lambda x:(x[0],-x[1]))

#y座標が大きい順にソート
Red =sorted(Red ,key=lambda x:-x[1])

ans=0
for x,y in Blue:
  for i,point in enumerate(Red):
    a,b=point
    if a<x and b<y:
      ans+=1
      del Red[i]
      break
print(ans)

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  ab = [list(map(int,input().split())) for _ in range(N)]
  cd = [list(map(int,input().split())) for _ in range(N)]
  ab = sorted(ab)
  cd = sorted(cd)
  cnt = 0
  i = 0
  while i < len(cd):
    x = cd[i][0]
    std = -1
    y = -1
    for j in range(len(ab)):
      if ab[j][0] < x and ab[j][1] > y and ab[j][1] < cd[i][1]:
        std = j
        y = ab[j][1]
    if std == -1:
      i += 1
      continue
    cd.pop(i)
    ab.pop(std)
    cnt += 1
  #print(ab)
  #print(cd)
  print(cnt)
  
main()

Submission status: Accepted

Solution code:
def find_most_rightup(c,d):
  tmpA = []
  for i in range(len(AB)):
    a,b = AB[i]
    if a<c and b<d:
      tmpA.append([b,i])
  if len(tmpA) > 0:
    return sorted(tmpA, reverse=True)[0][1]
  else: return None

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

CD = []
for _ in range(N):
  c,d = map(int,input().split())
  CD.append([c,d])

AB.sort(reverse=True)
CD.sort()
ans = 0
for c,d in CD:
  min_i = find_most_rightup(c,d)
  if min_i is not None:
    del AB[min_i]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
CD = [list(map(int, input().split())) for _ in range(N)]

cnt = 0
sCD = sorted(CD, key=lambda x: x[1])
for c, d in sCD:
  AB = sorted(AB, key=lambda x: - x[0])
#  print(AB)
  for itr in range(len(AB)):
    a, b = AB[itr]
    if a < c and b < d:
      cnt += 1
      AB.pop(itr)
      break
print(cnt)