Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All input values are integers.

1 \leq N \leq 100

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum number of friendly pairs.

Sample Input 1

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

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

2

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

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

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

Sample Output 4

5

Sample Input 5

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

Sample Output 5

4



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


Sample output:
2

Submission status: Accepted

Solution code:
n = int(input())
reds = sorted([list(map(int,input().split())) for i in range(n)],key=lambda reds: -reds[1])
blues = sorted([list(map(int,input().split())) for i in range(n)])

res = 0

for c,d in blues:
  for a,b in reds:
    if a<c and b<d:
      reds.remove([a,b])
      res+=1
      break
      
print(res)

Submission status: Accepted

Solution code:
import operator
import bisect

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=operator.itemgetter(0,1))
blue.sort(key=operator.itemgetter(0,1))
#print(red)
#print(blue)
count=0
for i in range(n):
  for j in reversed(range(len(red))):
    #print("j",j)
    if not red:
      break
    if red[j][0]<blue[i][0]:
      tmp=red[:j+1]
      tmp.sort(key=lambda x:x[1],reverse=True)
      for t in tmp:
        if t[1]<blue[i][1]:
          count+=1
          red.pop(red.index(t))
          #print("t",t,"blue[i]",blue[i])
          break
    else:
      continue
    break

print(count)

Submission status: Accepted

Solution code:
n = int(input())
aka = [[0 for i in range(2*n)] for j in range(2*n)]
for i in range(n):
    a, b = map(int,input().split())
    aka[a][b] = 1
ao = [tuple(map(int,input().split())) for i in range(n)]
ao.sort()
ans = 0
for x , y in ao:
    flag = False
    for j in reversed(range(y)):
        if flag:
            break
        for i in reversed(range(x)):
            if aka[i][j] == 1:
                ans += 1
                aka[i][j] = 0
                flag = True
                break
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

class Ford_Fulkerson:
    def __init__(self,G,N,s,t):
        self.G,self.N,self.s,self.t=G,N,s,t
        self.max_f=self.Max_Flow(self.G,self.s,self.t)
        
    def dfs(self,G,v,t,f,used):
        if v==t:
            return f
        used[v]=True
        for nv,cap in G[v].items():
            if not used[nv] and cap>0:
                d=self.dfs(self.G,nv,t,min(f,cap),used)
                if d>0:
                    self.G[v][nv]-=d
                    self.G[nv][v]+=d
                    return d
        return 0

    def Max_Flow(self,G,s,t):
        flow=0
        while(True):
            used=[False]*(2*N+2)
            f=self.dfs(self.G,self.s,self.t,float('inf'),used)
            if f==0:
                return flow
            flow+=f

N=int(input())
G=[defaultdict(int) for i in range(2*N+2)]
arr=[]
for i in range(2*N):
    x,y=map(int,input().split())
    arr.append((x,y))

for i in range(N,2*N):
    for j in range(N):
        a,b=arr[i]
        c,d=arr[j]
        if a>c and b>d:
            G[i+1][j+1]=1
            G[j+1][i+1]=0
for i in range(1,2*N+1):
    if i>=N+1:
        G[0][i]=1
        G[i][0]=0
    else:
        G[i][2*N+1]=1
        G[2*N+1][i]=0

MF=Ford_Fulkerson(G,2*N+2,0,2*N+1)
print(MF.max_f)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

class Ford_Fulkerson:
    def __init__(self,G,N,s,t,check):
        self.G,self.N,self.s,self.t,self.check=G,N,s,t,check
        for v in range(self.N):
            if v==s or v==t:
                continue
            for nv,cap in self.G[v].items():
                self.G[nv][v]=0
            if self.check(v):
                self.G[s][v]=1
                self.G[v][s]=0
            else:
                self.G[v][t]=1
                self.G[t][v]=0
        self.max_f=self.Max_Flow(self.G,self.s,self.t)
        
    def dfs(self,G,v,t,f,used):
        if v==t:
            return f
        used[v]=True
        for nv,cap in G[v].items():
            if not used[nv] and cap>0:
                d=self.dfs(self.G,nv,t,min(f,cap),used)
                if d>0:
                    self.G[v][nv]-=d
                    self.G[nv][v]+=d
                    return d
        return 0

    def Max_Flow(self,G,s,t):
        flow=0
        while(True):
            used=[False]*(2*N+2)
            f=self.dfs(self.G,self.s,self.t,float('inf'),used)
            if f==0:
                return flow
            flow+=f

N=int(input())
G=[defaultdict(int) for i in range(2*N+2)]
arr=[]
for i in range(2*N):
    x,y=map(int,input().split())
    arr.append((x,y))

for i in range(N,2*N):
    for j in range(N):
        a,b=arr[i]
        c,d=arr[j]
        if a>c and b>d:
            G[i+1][j+1]=1

def check(i):return i>=1+N
MF=Ford_Fulkerson(G,2*N+2,0,2*N+1,check)
print(MF.max_f)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def dfs(v,t,f,used):
    if v==t:
        return f
    used[v]=True
    for nv,cap in G[v].items():
        if not used[nv] and cap>0:
            d=dfs(nv,t,min(f,cap),used)
            if d>0:
                G[v][nv]-=d
                G[nv][v]+=d
                return d
    return 0

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

INF=float('inf')

N=int(input())
G=[defaultdict(int) for i in range(2*N+2)]
arr=[]
for i in range(2*N):
    x,y=map(int,input().split())
    arr.append((x,y))

for i in range(N,2*N):
    for j in range(N):
        a,b=arr[i]
        c,d=arr[j]
        if a>c and b>d:
            G[i+1][j+1]=1
            G[j+1][i+1]=0

for i in range(N):
    G[0][N+i+1]=1
    G[N+i+1][0]=0
    G[i+1][2*N+1]=1
    G[2*N+1][i+1]=0
res=Max_Flow(0,2*N+1)
print(res)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

class Dinic:
    def __init__(self, v):
        self.vertice = v
        self.inf = int(1e9)
        self.graph = [[] for i in range(v)]
        self.level = [0]*v
        self.iter = [0]*v
    
    def add_edge(self, fr, to, cap):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        self.graph[to].append([fr, 0, len(self.graph[fr])-1])
    
    def bfs(self, s):
        self.level = [-1]*self.vertice
        que = deque([])
        self.level[s] = 0
        que.append(s)

        while que:
            v = que.popleft()
            for i in range(len(self.graph[v])):
                e = self.graph[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.graph[v])):
            self.iter[v] = i
            e = self.graph[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.graph[e[0]][e[2]][1] += 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]*self.vertice

            f = self.dfs(s, t, self.inf)
            while f:
                flow += f
                f = self.dfs(s, t, self.inf)
    
def main():
    n = int(input())
    red = [list(map(int, input().split())) for _ in range(n)]
    blue = [list(map(int, input().split())) for _ in range(n)]
    
    flow = Dinic(n*2+2)
    for i in range(n):
        flow.add_edge(0, i+1, 1)
        flow.add_edge(n+i+1, 2*n+1, 1)
        for j in range(n):
            if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
                flow.add_edge(i+1, n+j+1, 1)
    
    
    ans = flow.max_flow(0, 2*n+1)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

blues = []
for i in range(N):
    c, d = map(int, input().split())
    blues.append([c,d])
blues.sort()

flag = [False for i in range(N)]
ans = 0
for i in range(N):
    c, d = blues[i][0], blues[i][1]
    for j in range(N):
        if flag[j] == True:
            continue
        a, b = reds[j][0], reds[j][1]
        if c>a and d>b:
            flag[j] = True
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
import networkx as nx

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

# 0 <= i <   N  -> i: ABs[i]
# N <= i < 2*N  -> i: CDs[i-N]
# i == 2*N+1    -> start
# i == 2*N+2    -> goal

DG = nx.DiGraph()
DG.add_nodes_from(range(2 * N + 3))
for i in range(N):
    for j in range(N):
        if ABs[i][0] < CDs[j][0] and ABs[i][1] < CDs[j][1]:
            DG.add_edge(i, j + N, capacity = 1)

DG.add_edges_from([(2 * N + 1, i, {"capacity":1}) for i in range(N)])
DG.add_edges_from([(i, 2 * N + 2, {"capacity":1}) for i in range(N, 2*N)])

print(nx.maximum_flow_value(DG, 2 * N + 1, 2 * N + 2))

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()
    
    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()
    blue.sort()

    now = 0
    for i in blue:
        while now < len(red) and red[now] < i:
            now += 1
        
        l = red[:now]
        if l == []:
            continue

        l = sorted(l, key=lambda x: x[1])
        if l[0][1] > i[1]:
            continue
        
        # binary search
        left = 0
        right = len(l) - 1
        while left < right:
            center = (left + right + 1) // 2
            if l[center][1] < i[1]:
                left = center
            else:
                right = center - 1

        red.remove(l[left])
        now -= 1

    print(n - len(red))

main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()
    
    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()
    blue.sort()

    now = 0
    for i in blue:
        while now < len(red) and red[now] < i:
            now += 1
        
        l = red[:now]
        if l == []:
            continue

        l = sorted(l, key=lambda x: x[1])
        for j in range(len(l)-1, -1, -1):
            if l[j][1] < i[1]:
                red.remove(l[j])
                now -= 1
                break

    print(n - len(red))

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# C - 2D Plane 2N Points
import sys 
from bisect import bisect,bisect_left
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
query = [(0,0)]*N*2
# 赤0 青1
for _ in range(N):
    a,b =map(int,readline().split())
    query[a] = (0,b)
for _ in range(N):
    a,b =map(int,readline().split())
    query[a] = (1,b)

A = []
ans = 0
for i in range(2*N):
    q,y = query[i]
    if q == 0:
        A.append(y)
        A = sorted(A)
    else:
        ind = bisect_left(A,y)
        if ind != 0:
            A.pop(ind-1)
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import networkx as nx


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


match_list = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        a, b = ab[i]
        c, d = cd[j]

        if a < c and b < d:
            match_list[i].append(j)
# print(match_list)


group1 = range(n)
group2 = range(n, 2*n)

g = nx.Graph()
g.add_nodes_from(group1, bipartite=1)
g.add_nodes_from(group2, bipartite=0)

for i, list_ in enumerate(match_list):
    for j in list_:
        g.add_edge(i, j+n, weight=1)

# A, B = bipartite.sets(g)
# print(A, B)
# pos = dict()
# pos.update((n, (1, i)) for i, n in enumerate(A))
# pos.update((n, (2, i)) for i, n in enumerate(B))
# nx.draw_networkx(g, pos)
# nx.draw_networkx_edges(g, pos)
# plt.axis("off")
# plt.show()


d = nx.max_weight_matching(g)

print(len(d))

Submission status: Accepted

Solution code:
def abc091_c():
    n = int(input())
    red = []
    blue = []
    for _ in range(n):
        a, b = (int(x) for x in input().split())
        red.append((a, b))
    for _ in range(n):
        c, d = (int(x) for x in input().split())
        blue.append((c, d))
    blue = sorted(blue, key=lambda x: x[0])

    ans = 0
    r_used = [False]*n
    for c, d in blue:
        match = -1
        y_high = -1
        for i, (a, b) in enumerate(red):
            if r_used[i]: continue
            if not (a < c and b < d): continue
            if y_high < b:
                match = i
                y_high = b
        if match != -1:
            ans += 1
            r_used[match] = True
    print(ans)

if __name__ == '__main__':
    abc091_c()

Submission status: Accepted

Solution code:
N = int(input())
Red = sorted([tuple(map(int, input().split())) for _ in range(N)])
Blue = sorted([tuple(map(int, input().split())) for _ in range(N)])

ans = 0
for bx,by in Blue:
    C = [(y,x) for x,y in Red if x<bx and y<by] #候補
    if len(C) == 0:
        continue
    ans += 1
    C.sort(reverse=True)
    Red.remove((C[0][1],C[0][0]))
print(ans)

Submission status: Accepted

Solution code:

n = int(input().strip())
red = [list(map(int, input().split())) for i in range(n)]
blue = [list(map(int, input().split())) for j in range(n)]

for i in range(n):
    '''
    kagi_r = [min(red[i][0], red[i][1]), max(red[i][0], red[i][1])]
    kagi_b = [min(blue[i][0], blue[i][1]), max(blue[i][0], blue[i][1])]
    red[i] = red[i] + kagi_r
    blue[i] = blue[i] + kagi_b
    '''
red.sort(key=lambda x: (x[0], x[1]), reverse=True)
blue.sort(key=lambda x: x[1])
flg_r = [0]*n
cnt = 0

for i in range(n):
    for j in range(n):
        if flg_r[j]:
            continue
        if red[j][0] < blue[i][0] and red[j][1] < blue[i][1]:
            flg_r[j] = 1
            cnt += 1
            break

print(cnt)

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()
ab.sort(key = lambda x: x[1], reverse = True)
flag_ab = [False for i in range(n)]
count = 0
for i in range(n):
    c, d = cd[i][0], cd[i][1]
    for j in range(n):
        if flag_ab[j] == True:
            continue
        a, b = ab[j][0], ab[j][1]
        if c > a and d > b:
            flag_ab[j] = True
            count += 1
            break
print(count)

Submission status: Accepted

Solution code:
n=int(input())
red=[[] for i in range(n)]
blue=[[] for i in range(n)]
for i in range(n):
    a,b=map(int,input().split())
    red[i].append(a)
    red[i].append(b)
for i in range(n):
    a,b=map(int,input().split())
    blue[i].append(a)
    blue[i].append(b)
red=sorted(red)
blue=sorted(blue)
ans=0
for i in range(n):
    x=blue[i][0]
    y=blue[i][1]
    maxy=-1
    for j in range(n):
        if x>red[j][0] and y>red[j][1]:
            maxy=max(maxy,red[j][1])
    for j in range(n):
        if x>red[j][0] and maxy==red[j][1]:
            ans+=1
            red[j][0]=1000
            break
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
(n, ), *dot = [[*map(int, i.split())] for i in open(0)]
red = sorted(dot[:n])
blue = sorted(dot[n:])
for c, d in blue:
    o = [[a, b] for a, b in red if a < c and b < d]
    if o:
        red.remove(max(o, key=lambda x: x[1]))
print(n - len(red))

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

# 青をx座標で昇順ソート
blue.sort(key=lambda x: x[1])

# 赤をy座標で降順ソート
red.sort(key=lambda x: x[0], reverse=True)

red_list = [0] * N

for b in range(N):
    for r in range(N):
        if red_list[r] == 1:
            continue
        if red[r][0] < blue[b][0] and red[r][1] < blue[b][1]:
            red_list[r] = 1
            break

print(sum(red_list))

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

# x座標でソート
blue.sort(key=lambda x: x[1])

# y座標で降順ソート
red.sort(reverse=True)

# print(blue)
# print(red)

# blue_list = [0] * N
red_list = [0] * N


for b in range(N):
    for r in range(N):
        if red_list[r] == 1:
            continue
        if red[r][0] < blue[b][0] and red[r][1] < blue[b][1]:
            # print(b, r)
            # blue_list[b] = 1
            red_list[r] = 1
            break

print(sum(red_list))

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

# x座標でソート
blue.sort(key=lambda x: x[1])

# y座標で降順ソート
red.sort(reverse=True)

# print(blue)
# print(red)

blue_list = [0] * N
red_list = [0] * N


for b in range(N):
    for r in range(N):
        if red_list[r] == 1:
            continue
        if red[r][0] < blue[b][0] and red[r][1] < blue[b][1]:
            # print(b, r)
            blue_list[b] = 1
            red_list[r] = 1
            break

print(sum(blue_list))

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)]
# y座標で降順ソート
red.sort(reverse=True)
# x座標でソート
blue.sort(key=lambda x: x[1])

# print(blue)
# print(red)
blue_list = [0] * N
red_list = [0] * N


for b in range(N):
    for r in range(N):
        if blue_list[b] == 1 or red_list[r] == 1:
            continue
        if red[r][0] < blue[b][0] and red[r][1] < blue[b][1]:
            # print(b, r)
            blue_list[b] = 1
            red_list[r] = 1
            break

print(sum(blue_list))

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,b in R:
    if a<c and b<d:
      R.remove([a,b]);ans+=1
      break
print(ans)

Submission status: Accepted

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
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=1): #つなぐノード2つ、容量
        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 = inf
        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())
dinic=Dinic(2*n+2)


A=[] ; B=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
for i in range(n):
    a,b=map(int,input().split())
    B.append([a,b])
for i in range(n):
    dinic.add_edge(2*n,i,1)
    dinic.add_edge(i+n, 2*n+1,1)
for i in range(n):
    for j in range(n):
        if A[i][0]<B[j][0] and A[i][1]<B[j][1]:
            dinic.add_edge(i,j+n)

print(dinic.flow(2*n,2*n+1))

Submission status: Accepted

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

for g in range(n):
    cd.append(tuple(map(int,input().split())))

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

ans = 0
for i in range(n):
    for g in range(n):
        if ab[i][0] < cd[g][0] and ab[i][1] < cd[g][1] and not used[g]:
            used[g] = True
            ans += 1
            break
print(ans)

Submission status: Accepted

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

paira=-1
pairb=-1
ans=0

for i in range(N):
	tempcd=CD[i]
	for h in range(len(AB)):
		tempab=AB[h]
		if tempab[0]<tempcd[0] and tempab[1]<tempcd[1]:
			if pairb<tempab[1]:
				paira=tempab[0]
				pairb=tempab[1]
				pairnum=h
	if paira!=-1 and pairb!=-1:
		ans+=1
		AB.pop(pairnum)
		paira=-1
		pairb=-1

print(ans)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
n = ni()
ab = []
for i in range(n):
    ab.append(lma())
ab.sort(key=lambda x:x[1],reverse=True)
ab.sort(reverse=True)
cd = []
for i in range(n):
    cd.append(lma())
cd.sort()
cd.sort(key=lambda x:x[1])
cnt=0
INF=10**9
for a,b in ab:
    #print("ab",a,b)
    for i in range(n):
        c,d = cd[i]
        if a<c and b<d:
            #print("cd",c,d)
            cnt+=1
            cd[i][0]=-INF
            cd[i][1]=-INF
            break
print(cnt)
#print(cd)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class FordFulkerson:
    def __init__(self, n):
        self.N = n
        self.G = [[] for _ 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())
    red = [list(map(int, input().split())) for _ in range(n)]
    blue = [list(map(int, input().split())) for _ in range(n)]
    
    flow = FordFulkerson(n*2+2)
    for i in range(n):
        flow.add_edge(0, i+1, 1)
        flow.add_edge(n+i+1, 2*n+1, 1)
        for j in range(n):
            if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
                flow.add_edge(i+1, n+j+1, 1)
    
    
    ans = flow.flow(0, 2*n+1)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
ab = [LIST() for _ in range(N)]
cd = [LIST() for _ in range(N)]

check = [0]*N
ab.sort(key = lambda x: (-x[0],-x[1]))
cd.sort(key = lambda x: (x[0], x[1]))

for c, d in cd:
	idx = -1
	tmp = INF
	for i in range(N):
		if check[i] == 0 and ab[i][0] < c and ab[i][1] < d and tmp > d-ab[i][1] :
			tmp = d-ab[i][1]
			idx = i
	if idx != -1:
		check[idx] = 1

print(sum(check))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li2(N)
B = li2(N)

A = sorted(A, key=lambda x:x[1])
B = sorted(B, key=lambda x:x[0])

flag = [0] * N

for i in range(N):
    ind = -1
    for j in range(N):
        if A[j][1] < B[i][1]:
            ind = j
    while ind >= 0:
        if not flag[ind] and A[ind][0] < B[i][0]:
            flag[ind] = 1
            break
        ind -= 1

#print(flag)
print(sum(flag))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
'''
N = ii()
A = li2(N)
B = li2(N)

A = sorted(A, key=lambda x:x[0])
B = sorted(B, key=lambda x:x[0])

a_ind = 0
b_ind = 0
cnt = 0

while b_ind < N:
    if A[a_ind][0] < B[b_ind][0] and  A[a_ind][1] < B[b_ind][1]:
        cnt += 1
        a_ind += 1
        b_ind += 1
    else:
        b_ind += 1

print(cnt)
'''
'''
#global ans
ans = 0

def dfs(a_ind, b_ind, cnt):
    if a_ind >= N or b_ind >= N:
        global ans
        ans = max(ans, cnt)
        return
    if A[a_ind][0] < B[b_ind][0] and  A[a_ind][1] < B[b_ind][1]:
        dfs(a_ind+1, b_ind+1, cnt+1)
    else:
        dfs(a_ind+1, b_ind, cnt)
        dfs(a_ind, b_ind+1, cnt)
        dfs(a_ind+1, b_ind+1, cnt)

dfs(0, 0, 0)

print(ans)
'''

# XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
#   edges[x]: xとつながるYの頂点のset
#   matched[y]: yとマッチングされたXの頂点(暫定)

def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False
 
 
# 標準入力からのグラフ読み取り
#xn, yn, e = map(int, input().split())
N = ii()
xn = N
yn = N
edges = [set() for _ in range(xn)]
matched = [-1] * yn
 
#for _ in range(e):
    #x, y = map(int, input().split())
    #edges[x].add(y)

A = li2(N)
B = li2(N)

for i in range(N):
    for j in range(N):
        if A[i][0] < B[j][0] and  A[i][1] < B[j][1]:
            edges[i].add(j)
 
# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(xn)))

Submission status: Accepted

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

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

ans = 0
for c, d in cd:
    for index, (a, b) in enumerate(ab):
        if a < c and b < d:
            ab[index] = (201, 201)
            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])
blue.sort()
count = 0
for xb, yb in blue:
    for i in range(n):
        if xb > red[i][0] and yb > red[i][1]:
            red[i] = (201, 201)
            count += 1
            break
print(count)