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: Time Limit Exceeded

Solution code:
N=int(input())
a=[0 for i in range(N)]
b=[0 for i in range(N)]
c=[0 for i in range(N)]
d=[0 for i in range(N)]
for i in range(N):
    a[i], b[i] = map(int, input().split())
for i in range(N):
    c[i], d[i] = map(int, input().split())
m=[[0 for i in range(N)] for i in range(N)]
s=[set() for i in range(N)]
for i in range(N):
    for j in range(N):
        if a[i]<c[j] and b[i]<d[j]:
            m[i][j]+=1
            s[i].add(j)
ans=0
import itertools
q=list(itertools.permutations(range(N)))
for sg in q:
    z=0
    for i in range(N):
        z+=m[i][sg[i]]
    if ans<z:
        ans=z
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    ab = [LI() for _ in range(N)]
    cd = [LI() for _ in range(N)]
    ab.sort()
    ab_used = collections.OrderedDict()
    for i in ab:
        ab_used[tuple(i)] = False
    cd.sort()

    # x座標でソート 青点基準で考える
    # 青点は、自分よりx座標が小さい赤点の中でy座標が最大のものをとればよい
    ans = 0
    for c, d in cd:
        m = -1
        m_ab = (-1, -1)
        for a, b in ab:
            if a > c:
                break
            if not ab_used[(a, b)] and d > b > m:
                m = b
                m_ab = (a, b)
        if m_ab != (-1, -1):
            ab_used[m_ab] = True
            ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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


class Dinic:
    """ 最大流(Dinic) """


    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        from collections import deque

        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, INF)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, INF)


def main():
    N = NI()
    R = [NLI() for _ in range(N)]
    B = [NLI() for _ in range(N)]
    din = Dinic(2*N+2)
    for a, b in R:
        for c, d in B:
            if a >= c or b >= d: continue
            din.add_link(a, c, 1)
    for a, b in R:
        din.add_link(2*N, a, 1)
    for c, d in B:
        din.add_link(c, 2*N+1, 1)
    print(din.max_flow(2*N, 2*N+1))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""
赤い点はできるだけ自分の座標に近い青い点と仲良しペアになった方がよい。
仲良しペアになれる候補が少ない赤点ほど、さきにみていった方がよい。
Nの上限が低いことを利用できそう。
解法１：
まず各赤点ごとに、ペアになれる青点を列挙する。  

解法２：
青、赤を混合した状態でXで降順ソートする。
一つずつ座標を見ていく。
ピックアップした座標が青色の場合、Y座標の情報をqueに入れる。
このとき、queの中身が昇順になるように、bisectを使ってqueに入れる。O(N)
ピックアップした座標が赤色の場合、queの中に自分のY座標より大きい値があるかを探し、あればそれを取り出す。O(N)
全体はO(N^2)で実行可能
"""
from bisect import insort
N = int(input())
coordinates = []
for _ in range(N):
    a,b = map(int,input().split())
    coordinates.append((a,b,0))
for _ in range(N):
    c,d = map(int,input().split())
    coordinates.append((c,d,1))

coordinates.sort(reverse=True)
que = []
ans = 0
for x,y,c in coordinates:
    if c:
        insort(que,y)
    else:
        if que and que[-1] > y:
            ans += 1
            for i in range(len(que)):
                if que[i] > y:
                    que = que[:i]+que[i+1:]
                    break
print(ans)

Submission status: Accepted

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


b.sort()

l=[0 for i in range(n)]
c=0
for i in range(n):
  m,t=-1,-1
  for j in range(n):
    if l[j]:
      continue
    if a[j][0]<b[i][0] and a[j][1]<b[i][1] and m<a[j][1]:
      m=a[j][1]
      t=j
  if t!=-1:
    l[t]=1
  c+=t!=-1
print(c)

Submission status: Accepted

Solution code:
n=int(input())
za=[[0 for _ in range(2*n)] for _ in range(2*n)]

al=[]
for _ in range(n):
  a,b=(map(int,input().split()))
  za[a][b]+=1
  
bl=[]

for _ in range(n):
  b=list(map(int,input().split()))
  bl.append(b)
  
bl.sort()

ans=0

for v in bl:
  x,y=v
  tempy=-1
  for z in range(0,x):
    for u in range(0,y):
      if za[z][u]>=1:
        if u>tempy:
          tempx=z
          tempy=u
  if tempy>=0:
    ans+=1
    za[tempx][tempy]-=1
    
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

    ball = []
    for i in range(N):
        a, b = map(int, input().split())
        ball.append([a,b,'r'])
    for i in range(N):
        c, d = map(int, input().split())
        ball.append([c,d,'b'])

    sort_ball = sorted(ball, key=lambda x:(-x[0],x[1]))
    ans = 0
    cand = []
    for i in range(2*N):
        if sort_ball[i][2] == 'b':
            cand.append(sort_ball[i][1])
        if sort_ball[i][2] == 'r':
            if not cand:
                continue
            cand.sort()
            b_y = bisect_left(cand, sort_ball[i][1])
            if b_y == len(cand):
                continue
            ans += 1
            cand.pop(b_y)

    print(ans)

        

    
    
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Weigthed_Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

def Flow(D,source,sink):
    s,t=source,sink

    H={v:[] for v in D.vertex}

    for u in D.vertex:
        for v in D.adjacent_out[u]:
            F=[v,D.adjacent_out[u][v],None]
            F[2]=B=[u,0,F]
            H[u].append(F)
            H[v].append(B)

    def dfs(v,t,f):
        if v==t:
            return f

        U[v]=True
        for e in H[v]:
            w,cap,inv=e

            if cap and (not U[w]):
                d=dfs(w,t,min(f,cap))
                if d:
                    e[1]-=d
                    inv[1]+=d
                    return d
        return 0

    inf=float("inf")
    f=inf
    flow=0
    while f:
        U={v:False for v in D.vertex}
        f=dfs(s,t,inf)
        flow+=f
    return flow

#================================================
N=int(input())

R=[0]*N
for i in range(N):
    a,b=map(int,input().split())
    R[i]=(a,b)

B=[0]*N
for i in range(N):
    c,d=map(int,input().split())
    B[i]=(c,d)

D=Weigthed_Digraph([c*k for k in range(1,N+1) for c in [1,-1]])

for i in range(1,N+1):
    D.add_edge("s",i,1)
    D.add_edge(-i,"t",1)

for i in range(N):
    a,b=R[i]
    for j in range(N):
        c,d=B[j]

        if a<c and b<d:
            D.add_edge(i+1,-(j+1),1)

print(Flow(D,"s","t"))

Submission status: Accepted

Solution code:
n = int(input())
ab = set(tuple(map(int, input().split())) for _ in range(n))
cd = sorted(tuple(map(int, input().split())) for _ in range(n))
ab |= {(-1, -1)}

ans = 0
for c, d in cd:
    tmp = max((b, a) for a, b in ab if (a < c and b < d))
    if tmp != (-1, -1):
        ab.remove(tmp[::-1])
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab = set(tuple(map(int, input().split())) for _ in range(n))
cd = sorted(tuple(map(int, input().split())) for _ in range(n))
ab |= {(-1, -1)}

ans = 0
for c, d in cd:
    tmp = max((b, a) for a, b in ab if (a < c and b < d))
    if tmp != (-1, -1):
        ab.remove(tmp[::-1])
        ans += 1
print(n - (len(ab) - 1))

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()
ans = 0
for i in cd:
    c, d = i
    flag = False
    cur = 0
    difference = float("inf")
    for i in range(n):
        a, b = ab[i]
        if a < c and b < d:
            if difference > d - b:
                difference = min(difference, d - b)
                flag = True
                cur = i
    if flag:
        ab[cur] = [float("inf"), float("inf")]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab = set(tuple(map(int, input().split())) for _ in range(n))
cd = sorted(tuple(map(int, input().split())) for _ in range(n))

ab |= {(-1, -1)}
for c, d in cd:
    tmp = max((b, a) for a, b in ab if (a < c and b < d))
    if tmp != (-1, -1):
        ab.remove(tmp[::-1])
print(n - (len(ab) - 1))

Submission status: Accepted

Solution code:
n = int(input())
ab = set(tuple(map(int, input().split())) for _ in range(n))
cd = sorted(tuple(map(int, input().split())) for _ in range(n))

ab |= {(-1, -1)}
for c, d in cd:
    tmp = max((b, a) for a, b in ab if (a < c and b < d))[::-1]
    if tmp != (-1, -1):
        ab.remove(tmp)
print(n - (len(ab) - 1))

Submission status: Accepted

Solution code:
N = int(input())
Red = dict()
Redyset = set()
for _ in range(N):
    a,b = map(int,input().split())
    Red[b] = a
    Redyset.add(b)
Blue = dict()
Bluexset = set()
for _ in range(N):
    c,d = map(int,input().split())
    Blue[c] = d
    Bluexset.add(c)
Ans = 0
for i in range(N):
    Blx = min(Bluexset)
    Bluexset.remove(Blx)
    Bly = Blue.pop(Blx)
    Ymax = -1
    for Rey in Redyset:
        if Blx > Red[Rey] and Bly > Rey:
            Ymax = max(Ymax,Rey)
    if Ymax != -1:
        Redyset.remove(Ymax)
        Rey = Red.pop(Ymax)
        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)]

AB = sorted(AB, key=lambda x: -x[0])
CD = sorted(CD, key=lambda x: x[1])

ans  = 0
for a,b in AB:
    for key,val in enumerate(CD):
        c,d = val[0],val[1]
        if a < c and b < d:
            CD.pop(key)
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=[list(map(int,input().split())) for i in range(N)]
V=N*2+2
G=[[] for i in range(V)]
L=[0]*V
I=[0]*V
INF=10**15
def ae(fr,to,ca):
  global G
  G[fr].append([to,ca,len(G[to])])
  G[to].append([fr,0,len(G[fr])-1])

def bfs(s):
  global INF,L,V,G
  L=[-1]*V
  Q=deque()
  L[s]=0
  Q.append(s)
  while(len(Q)):
    x=Q.popleft()
    for i in range(len(G[x])):
      if G[x][i][1]>0 and L[G[x][i][0]]<0:
        L[G[x][i][0]]=L[x]+1
        Q.append(G[x][i][0]) 

def dfs(v,t,f):
  global I,G,V
  if v==t:
    return f
  for i in range(I[v],len(G[v])):
    if G[v][i][1]>0 and L[v]<L[G[v][i][0]]:
      d=dfs(G[v][i][0],t,min(f,G[v][i][1]))
      if d>0:
        G[v][i][1]-=d
        G[G[v][i][0]][G[v][i][2]][1]+=d
        return d
    I[v]+=1
  return 0

def mf(s,t):
  global L,I,INF,V
  fl=0
  while(True):
    bfs(s)
    if L[t]<0:
      break
    I=[0]*V
    f=0
    while(True):
      f=dfs(s,t,INF)
      if f<=0:
        break
      fl+=f
  return fl

for i in range(N):
  ae(0,i+1,1)
  ae(N+i+1,N*2+1,1)
  for j in range(N):
    if A[i][0]<B[j][0] and A[i][1]<B[j][1]:
      ae(i+1,N+j+1,1)
print(mf(0,N*2+1))

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

red.sort()
blue.sort(reverse=1)
cnt =0

while blue:
    a,b = blue.pop()
    idx = -1
    tmp = -1
    for ai in range(len(red)):
        if red[ai][0]>a:
                break
        else:
            if red[ai][1]>tmp and red[ai][1]<b:
                idx=ai
                tmp = red[ai][1]
    if idx != -1:
        red.pop(idx)
        cnt +=1
print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
import copy
import random
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy

def solve():
    n = getN()
    anums = []
    bnums = []
    for i in range(n):
        anums.append(getList() + [0])
    for i in range(n):
        anums.append(getList() + [1])

    anums.sort()
    aaa = []
    ans = 0
    for num in anums:
        x, y, b = num
        if b == 0:
            aaa.append(y)
            aaa.sort()
        else:
            id = bisect_left(aaa, y)
            if id != 0:
                ans += 1
                del aaa[id-1]
    print(ans)
    #
    # an = [(max(x[0], x[1]), 0) for x in anums]
    # bn = [(min(x[0], x[1]), 1) for x in bnums]
    #
    # li = []
    # for ann in an:
    #     li.append(ann)
    # for bnn in bn:
    #     li.append(bnn)
    #
    # li.sort()
    # ac = 0
    # ans = 0
    # for l in li:
    #     if l[1] == 0:
    #         ac += 1
    #     else:
    #         if ac:
    #             ans += 1
    #             ac -= 1
    #
    # print(ans)


def main():
    n = getN()
    for _ in range(n):
        s = "".join([random.choice(["F", "T"]) for i in range(20)])
        print(s)
        solve(s, 1, 0)

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
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,key=lambda x: x[0])
cd=sorted(cd,key=lambda x: x[0])
s=set()
ans=0
for i in range(n):
    c,d=cd[i]
    y=-1
    for j in range(n):
        a,b=ab[j]
        if a<c and b<d:
            if y<b and j not in s:
                y=b
                ind=j
    if y!=-1:
        s.add(ind)
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    for i in range(2 * N):
        R[i].sort(reverse=True)
        B[i].sort(reverse=True)

    ans = 0
    Bx = 1
    for By_list in B[1:]:
        for By in By_list:
            Rx = Bx - 1
            max_Ry = [-1, -1]
            for Ry_list in R[:Rx + 1][::-1]:
                for Ry in Ry_list:
                    if max_Ry[1] < Ry < By:
                        max_Ry = [Rx, Ry]
                Rx -= 1
            if max_Ry[1] != -1:
                ans += 1
                R[max_Ry[0]].remove(max_Ry[1])
        Bx += 1

    print(ans)


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.sort()
cd.sort()

# xが小さい順に組む
# cdの前から見ていく, 組めるもののうち、yが最大のものを組むと
# そのペアをcd[i], ab[j]とする。
# まず別のcd[k]を考える。
# x, y共にcdよりでかい場合、交換可能
# xのみでかい場合, yが足りなくて組めないことがある
# yのみでかい場合, x昇順に見てるので、cd[i][0]==cd[k][0], 交換可能
# 悪化しないのでおk
ans = 0
used = [False] * n
for i in range(n):
    max_idx = -1
    max_y = -1
    for j in range(n):
        if not used[j] and ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1] and max_y < ab[j][1]:
            max_idx = j
            max_y = ab[j][1]
    if max_idx != -1:
        used[max_idx] = True
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from abc import abstractmethod
from collections import defaultdict
from math import inf


class Edge:
    def __init__(self):
        self.flow = 0
        self.residual: Edge
        self.from_node = None
        self.to_node = None
        self.capacity = None

    @classmethod
    def by_nodes(cls, from_node, to_node, capacity):
        c = cls()
        c.connect(from_node, to_node, capacity)
        return c

    def connect(self, from_node, to_node, capacity):
        self.from_node = from_node
        self.to_node = to_node
        self.capacity = capacity

    def is_residual(self):
        return self.capacity == 0

    def remaining_capacity(self):
        return self.capacity - self.flow

    def augument(self, bottle_neck):
        self.flow += bottle_neck
        self.residual.flow -= bottle_neck

    def __repr__(self):
        return f"{self.from_node}-({self.flow}/{self.capacity})->{self.to_node}"


class NetworkFlowSolverBase:
    def __init__(self, n, s, t):
        self.visited_token = 1
        self.visited = defaultdict(int)
        self.solved = False
        self.max_flow = 0
        self.graph = defaultdict(list)
        # n: the number of nodes in the graph including s(src) and t(sink)
        self.n = n
        # s: the index of the src node
        self.s = s
        # t: the index of the sink node
        self.t = t

    def add_edge(self, from_node, to_node, capacity):
        assert capacity >= 0, f"forward-edge capacity must be >= 0: input={capacity}"
        e_f = Edge.by_nodes(from_node, to_node, capacity)
        e_b = Edge.by_nodes(to_node, from_node, 0)
        e_f.residual = e_b
        e_b.residual = e_f
        self.graph[from_node].append(e_f)
        self.graph[to_node].append(e_b)

    def get_graph(self):
        self.execute()
        return self.graph

    def get_max_flow(self):
        self.execute()
        return self.max_flow

    def execute(self):
        if self.solved:
            return
        self.solve()
        self.solved = True

    @abstractmethod
    def solve(self):
        pass


class FordFulkersonDfsSover(NetworkFlowSolverBase):
    def __init__(self, n, s, t):
        super().__init__(n, s, t)

    def solve(self):
        while True:
            f = self.dfs(self.s, inf)
            self.visited_token += 1
            self.max_flow += f
            if f == 0:
                break

    def dfs(self, nd, flow):
        if nd == self.t:
            return flow
        self.visited[nd] = self.visited_token

        for e in self.graph[nd]:
            if (
                e.remaining_capacity() > 0
                and self.visited[e.to_node] != self.visited_token
            ):
                bottle_neck = self.dfs(e.to_node, min(flow, e.remaining_capacity()))
                if bottle_neck > 0:
                    e.augument(bottle_neck)
                    return bottle_neck
        return 0


if __name__ == "__main__":
    N = int(input())
    reds = [tuple(map(int, input().split())) for _ in range(N)]
    blues = [tuple(map(int, input().split())) for _ in range(N)]
    s = 2 * N
    t = 2 * N + 1
    G = FordFulkersonDfsSover(2 * N + 2, s, t)
    [G.add_edge(s, r, 1) for r in range(N)]
    [G.add_edge(b, t, 1) for b in range(N, 2 * N)]
    for r, (rx, ry) in enumerate(reds):
        for b, (bx, by) in enumerate(blues, N):
            if rx < bx and ry < by:
                G.add_edge(r, b, 1)

    print(G.get_max_flow())

Submission status: Accepted

Solution code:
import networkx as nx

N = int(input())
reds = [tuple(map(int, input().split())) for _ in range(N)]
blues = [tuple(map(int, input().split())) for _ in range(N)]
G = nx.DiGraph()
for rx, ry in reds:
    for bx, by in blues:
        if rx < bx and ry < by:
            G.add_edge("S", (rx, ry), capacity=1)
            G.add_edge((rx, ry), (bx, by), capacity=1)
            G.add_edge((bx, by), "T", capacity=1)
if G.nodes:
    print(nx.maximum_flow_value(G, "S", "T"))
else:
    print(0)

Submission status: Accepted

Solution code:
import networkx as nx
from networkx.algorithms.flow import dinitz

N = int(input())
reds = [tuple(map(int, input().split())) for _ in range(N)]
blues = [tuple(map(int, input().split())) for _ in range(N)]
G = nx.DiGraph()
for rx, ry in reds:
    for bx, by in blues:
        if rx < bx and ry < by:
            G.add_edge("S", (rx, ry), capacity=1)
            G.add_edge((rx, ry), (bx, by), capacity=1)
            G.add_edge((bx, by), "T", capacity=1)
if G.nodes:
    R = dinitz(G, "S", "T")
    print(R.graph["flow_value"])
else:
    print(0)

Submission status: Accepted

Solution code:
n = int(input())
r = [tuple(map(int, input().split())) for i in range(n)]
b = [tuple(map(int, input().split())) for i in range(n)]
r.sort(key=lambda x: x[1], reverse=True) # yの降順
b.sort(key=lambda x: x[0])
used = [0]*n

ans = 0
for i in range(n):
    bx,by = b[i]
    j = 0
    while j < n:
        rx,ry = r[j]
        if rx < bx and ry < by and used[j] == 0:
            ans += 1
            used[j] = 1
            break
        j += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
AB = []
for i in range(n):
    a, b = map(int, input().split())
    AB.append((a, b))
CD = []
for i in range(n):
    c, d = map(int, input().split())
    CD.append((c, d))

AB.sort(key=lambda x:-x[1])
CD.sort()

#print(AB)
#print(CD)

ans = 0
used = set()
for i in range(n):
    c, d = CD[i]
    for j in range(n):
        if j in used:
            continue
        a, b = AB[j]
        if a < c and b < d:
            ans += 1
            used.add(j)
            break
print(ans)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, AB, CD):
    ans = 0
    AB.sort(key=lambda x: x[0], reverse=True)
    for a, b in AB:
        CD.sort(key=lambda x: x[1])
        idx = 0
        while idx < len(CD):
            c, d = CD[idx]
            if a < c and b < d:
                break
            idx += 1
        else:
            continue
        ans += 1
        del CD[idx]
    print(ans)


if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, AB, CD)

Submission status: Accepted

Solution code:
n = int(input())
rl = []
bl = []
xs = [(-1,'',False)]*(2*n)
for _ in range(n):
    a,b = map(int, input().split())
    rl.append((a,b))
    xs[a] = (b,'r',False)


for _ in range(n):
    c,d = map(int, input().split())
    bl.append((c,d))
    xs[c] = (d,'b',False)

rl.sort(reverse=True)
bl.sort()

ans = 0
for rx,ry in rl:
    min_x,min_y = 10**5,10**5
    for x in range(rx,2*n):
        y,color,used = xs[x]
        if y > ry and color =='b' and not used and min_y > y:
            min_x = x
            min_y = y
    if min_x != 10**5:
        ans += 1
        xs[min_x] = (min_y,'b',True)

print(ans)