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:
# coding: utf-8
# hello worldと表示する
import sys
import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lisr=[LI() for i in range(n)]
lisb=[LI() for i in range(n)]
#print(lisr)
#print(lisb)
lisr.sort(key=itemgetter(1))
lisb.sort(key=itemgetter(1))
#print(lisr)
#print(lisb)
count=0
for i in range(n):
    x,y=lisb[i]
    mx=-inf
    for j in range(n):
        a,b=lisr[j]
        if b<y and a<x:
            if a>mx:
                mx=a
                pos=j
    #print(mx,pos)
    if mx>-inf:
        count+=1
        lisr[pos][1]=inf
print(count)
#print(lisr)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    # 赤が青の左下にあるようなペアを最大幾つとれるか
    # 全ての点のx,yそれぞれが同じ値になる事はない
    # bluesの左側から見ていって、その点より左下のredsがあるならその中でyが一番大きいものをとる
    reds,blues = [],[]
    for i in range(N):
        a,b = map(int,input().split())
        reds.append([a,b])
    for i in range(N):
        c,d = map(int,input().split())
        blues.append([c,d])
    reds = sorted(reds, key=lambda x:-x[1])
    blues = sorted(blues, key=lambda x:x[0])
    ans = 0
    for i in range(N):
        flag = False
        for j,r in enumerate(reds):
            if blues[i][0]>r[0] and blues[i][1]>r[1]:
                flag = True
                reds.pop(j)
                ans += 1
                break
    print(ans)

main()

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)
b.sort(key=lambda x: x[0])
selected=[0]*n

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

Submission status: Accepted

Solution code:
from operator import itemgetter


n = int(input())
red = {tuple(int(i) for i in input().split()): False for _ in range(n)}
blue = {tuple(int(i) for i in input().split()): False for _ in range(n)}
c = 0
for b in sorted(blue.keys()):
    for r in sorted(red.keys(), key=itemgetter(1), reverse=True):
        if not red[r] and b[0] > r[0] and b[1] > r[1]:
            red[r] = True
            blue[b] = True
            c += 1
            break
print(c)

Submission status: Accepted

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

c = 0
for i in range(len(ps)):
    b = ps[i]
    # redもしくは、既にペアが決まっていたら飛ばす
    if b[2] == 0 or b[2] == 2:
        continue

    j = 0
    maxy = -1
    rec = -1
    while j < i:
        r = ps[j]
        # blue もしくは、既にペアが決まっていたら飛ばす
        if r[2] == 1 or r[2] == 2:
            j += 1
            continue

        if r[1] > maxy and r[1] < b[1]:
            maxy = r[1]
            rec = j
        j += 1
    if rec == -1:
        continue
    
    # ペアになったものを記録
    ps[rec][2] = 2
    c += 1
print(c)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
import numpy as np
n=int(input())
graph=np.zeros((2*n+2,2*n+2),dtype=np.int64)
start,goal=0,2*n+1
l=[[int(j)for j in input().split()]for i in range(n)]
for i in range(1,1+n):
    c,d=map(int,input().split())
    for j,(a,b) in enumerate(l,n+1):
        if a<c and b<d:
            graph[start,i]=1
            graph[i,j]=1
            graph[j,goal]=1
def max_flow(graph):
    flow=0
    while True:
        dist,pred=dijkstra(graph,indices=start,return_predecessors=True,unweighted=True)
        if dist[goal]==np.inf:
            return flow
        path=[]
        v=goal
        while True:
            path.append((pred[v],v))
            v=pred[v]
            if v==start:
                break
        add_flow=min(graph[x][y] for x,y in path)
        for x,y in path:
            graph[x][y]-=add_flow
            graph[y][x]+=add_flow
        flow+=add_flow
print(max_flow(graph))

Submission status: Accepted

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

count = 0
for c, d in sorted(blue_point_list, key=lambda x: x[0]):
    tmp_index = 0
    tmp_y = -1
    for i, p in enumerate(red_point_list):
        if c > p[0] and d > p[1]:
            if p[1] >= tmp_y:
                tmp_index = i
                tmp_y = p[1]

    if tmp_y > -1:
        count += 1
        red_point_list.pop(tmp_index)

print(count)

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(key=lambda x:x[0])
ab.sort(key=lambda x:x[1],reverse=True)
ab.sort(key=lambda x:x[0])
tmp = -1
ans = 0
for i in range(n):
    ma = -1
    for j in range(n):
        if cd[i][0] > ab[j][0]:
            if ab[j][1] > ma and cd[i][1] > ab[j][1]:
                ma = ab[j][1]
                tmp = j
    if tmp != -1:
        ans+=1
        ab[tmp][1] = 201
    tmp = -1
    ma = -1
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


class BipartiteMatch(object):

    def __init__(self, n):
        self.n = n
        self.conns = [[] for _ in range(n)]
        self.matched = [-1] * n
        self.visited = None
    def add_edge(self, s, t):
        self.conns[s].append(t)
        self.conns[t].append(s)

    def _dfs(self, i):
        self.visited[i] = True
        for j in self.conns[i]:
            k = self.matched[j]
            if (k < 0 or (not self.visited[k] and self._dfs(k))):
                self.matched[i] = j
                self.matched[j] = i
                return True
        return False

    def run(self):
        ret = 0
        for i in range(self.n):
            if self.matched[i] >= 0:
                continue
            self.visited = [False] * self.n
            if self._dfs(i):
                ret += 1
        return ret

def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    bm = BipartiteMatch(N * 2)
    for i, (x, y) in enumerate(zip(a, b)):
        for j, (xx, yy) in enumerate(zip(c, d)):
            if x < xx and y < yy:
                #print(i, N + j)
                bm.add_edge(i, N + j)
    ret = bm.run()
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [int()] * (N)  # type: "List[int]"
    d = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, a, b, c, d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
R=[list(map(int,input().split())) for i in range(N)]
B=[list(map(int,input().split())) for i in range(N)]
R=sorted(R,key=lambda x:x[0])
B=sorted(B,key=lambda x:x[0])
ir=0
ans=0
X=[]
for ib in range(N):
  while ir<N and R[ir][0]<=B[ib][0]:
    X.append(R[ir][1])
    ir+=1
  X=sorted(X)
  ix=len(X)-1
  while ix>=0 and X[ix]>=B[ib][1]:
    ix-=1
  if ix!=-1:
    X.pop(ix)
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
R = [list(map(int, input().split())) for _ in range(n)]
B = [list(map(int, input().split())) for _ in range(n)]
R.sort()
B.sort()
pair = []

for bx, by in B:
    tmp = [r for r in R if r[0] < bx]
    tmp.sort(key=lambda x: x[1])
    for rx, ry in tmp[::-1]:
        if ry < by:
            pair.append([[rx, ry], [bx, by]])
            R.pop(R.index([rx, ry]))
            break

print(len(pair))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
R = ILL(N)
B = ILL(N)

class Dinic:
  def __init__(self, N):
    self.N = N
    self.G = [[] for _ in range(N)]
    self.d = [0 for _ in range(N)]
    self.iter = [0 for _ in range(N)]

  def add(self, f, t, c):
    self.G[f].append({'to':t, 'cap':c, 'rev':len(self.G[t])})
    self.G[t].append({'to':f, 'cap':0, 'rev':len(self.G[f])-1})

  def bfs(self, s):
    self.d = [-1 for _ in range(self.N)]
    self.d[s] = 0;
    q = deque([s])
    while q:
      v = q.popleft()
      for e in self.G[v]:
        if e['cap'] > 0 and self.d[e['to']] < 0:
          self.d[e['to']] = self.d[v] + 1
          q.append(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.d[v] < self.d[e['to']]:
        r = self.dfs(e['to'], t, min(INF, e['cap']))
        if r > 0:
          e['cap'] -= r
          self.G[e['to']][e['rev']]['cap'] += r
          return r
    return 0

  def max_flow(self, s, t):
    flow = 0
    while True:
      self.bfs(s)
      if self.d[t] < 0:
        return flow
      self.iter = [0 for _ in range(self.N)]
      f = self.dfs(s,t,INF)
      while f > 0:
        flow += f
        f = self.dfs(s,t,INF)  
        
graph = Dinic(N*2+2)
for i in range(N):
  for j in range(N):
    if R[i][0] < B[j][0] and R[i][1] < B[j][1]:
      graph.add(i,j+N,1)
for i in range(N):
  graph.add(2*N,i,1)
  graph.add(i+N,2*N+1,1)

print(graph.max_flow(2*N,2*N+1))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
R = ILL(N)
B = ILL(N)

class Dinic:
  def __init__(self, N):
    self.N = N
    self.G = [[] for _ in range(N)]
    self.level = [0 for _ in range(N)]
    self.iter = [0 for _ in range(N)]

  def add(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.N)]
    self.level[s] = 0;
    q = deque([s])
    while q:
      v = q.popleft()
      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
          q.append(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(INF, 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.N)]
      f = self.dfs(s,t,INF)
      while f > 0:
        flow += f
        f = self.dfs(s,t,INF)  
        
graph = Dinic(N*2+2)
for i in range(N):
  for j in range(N):
    if R[i][0] < B[j][0] and R[i][1] < B[j][1]:
      graph.add(i,j+N,1)
for i in range(N):
  graph.add(2*N,i,1)
  graph.add(i+N,2*N+1,1)

print(graph.max_flow(2*N,2*N+1))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
R = ILL(N)
B = ILL(N)

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

    def __init__(self, N):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.level = [0 for _ in range(N)]
        self.iter = [0 for _ in range(N)]

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

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.N)]
        self.level[s] = 0;
        q = deque([s])
        while q:
            v = q.popleft()
            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
                    q.append(e['to'])

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

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            # bfsで到達不可
            if self.level[t] < 0 : return flow
            self.iter = [0 for _ in range(self.N)]
            f = self.dfs(s,t,INF)
            while f > 0:
                flow += f
                f = self.dfs(s,t,INF)  
        
graph = Dinic(N*2+2)
for i in range(N):
  for j in range(N):
    if R[i][0] < B[j][0] and R[i][1] < B[j][1]:
      graph.add(i,j+N,1)
for i in range(N):
  graph.add(2*N,i,1)
  graph.add(i+N,2*N+1,1)

print(graph.max_flow(2*N,2*N+1))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))
"""lines:グラフの隣接リスト　dict型　lines[s]に辺が入る　defaultdict(set)で作る
 cost:辺の間の容量
 N：nodeの数（最終インデックスでない）
 start:sorceのnode
 Goal:sinkのnode"""
def ford_fulkerson(lines,cost,N,start,Goal):#linesとcostは上のように受け取っておく
     ans = 0
     INF = float('inf')
     def ford_in(s):#listはミュータブルだからnonlocalにしなくて良い
         nonlocal ans
         route = [0]*N
         ed = [True]*N
         ed[s] = False
         route[s] = -1
         que = deque([])
         que.append([s,INF])
         while que:
             s,flow = que.pop()
             for t in lines[s]:
                 if ed[t]:
                     flow = min(flow,cost[s][t])
                     que.append([t,flow])
                     ed[t] = False
                     route[t] = s
                     if t == Goal:
                         ans += flow
                         break
             else:
                 continue
             break
         else:
             return False

         t = Goal
         s = route[t]
         while s != -1:
             cost[s][t] -= flow
             if cost[s][t] ==0:
                 lines[s].remove(t)
             if cost[t][s] ==0:
                 lines[t].add(s)
             cost[t][s] += flow
             t = s
             s = route[t]

         return True

     while True:
         if ford_in(start):
             continue
         else:
             break
     return ans

N = int(input())
red = []
blue = []
for _ in range(N):
    a,b = inpl()
    red.append((a,b))
for _ in range(N):
    c,d = inpl()
    blue.append((c,d))

lines = defaultdict(set)
nnum = 2*N+2
cost = [[0]*nnum for i in range(nnum)]
for j in range(1,N+1):
    lines[0].add(j)
    cost[0][j] = 1
for k in range(N+1,2*N+1):
    lines[k].add(2*N + 1)
    cost[k][2*N+1]=1
for rd,r in enumerate(red):
    for bd,b in enumerate(blue):
        if (r[0] < b[0]) and (r[1]<b[1]):
            lines[rd+1].add(bd+1+N)
            cost[rd+1][bd+1+N]=1

print(ford_fulkerson(lines,cost,2*N+2,0,2*N+1))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def S(): return sys.stdin.readline().rstrip()

N = I()
ab = [tuple(int(j) for j in S().split()) for i in range(N)]
cd = [tuple(int(j) for j in S().split()) for i in range(N)]

from operator import itemgetter

ab = sorted(ab,key=itemgetter(1))
cd = sorted(cd,key=itemgetter(0))

ans = 0
for c,d in cd:
    A = []
    for i in range(N):
        if ab[i][0] < c and ab[i][1] < d:
            A.append(ab[i])
    if len(A) == 0:
        continue
    else:
        ans += 1
        for i in range(N):
            if ab[i] == A[-1]:
                ab[i] = (200,200)
                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()
chk = [False] * n

for b in blue:
    for i, r in enumerate(red):
        if chk[i]:
            continue
        elif r[0] < b[0] and r[1] < b[1]:
            chk[i] = True
            break
print(sum(chk))

Submission status: Accepted

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

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

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

red.sort(key=lambda x:x[1], reverse=True)
blue.sort()
chk = [False] * n

for b in blue:
    for i, r in enumerate(red):
        if chk[i]:
            continue
        elif r[0] < b[0] and r[1] < b[1]:
            chk[i] = True
            break
print(sum(chk))

Submission status: Accepted

Solution code:
N = int(input())
xs = []
ys = []

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

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

used = []
ret = 0
for (c, d) in ys:
    ab = None
    for (a, b) in xs:
        if a < c and b < d and used.count((a, b)) == 0:
            if ab is None:
                ab = (a, b)
            elif ab[1] < b:
                ab = (a, b)

    if ab is not None:
        used.append(ab)
        ret += 1

print(ret)

Submission status: Accepted

Solution code:
N = int(input())
xs = []
ys = []

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

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

used = []
ret = 0
for (c, d) in ys:
    l = []
    for (a, b) in xs:
        if a < c and b < d:
            l.append((a, b))

    ab = None
    for (a, b) in l:
        if used.count((a, b)) == 1:
            continue
        if ab is None:
            ab = (a, b)
        elif ab[1] < b:
            ab = (a, b)

    if ab is not None:
        used.append(ab)
        ret += 1

print(ret)

Submission status: Accepted

Solution code:
n = int(input())
p = [list(map(int,input().split()))+[0] for _ in range(n)]
p += [list(map(int,input().split()))+[1] for _ in range(n)]
p.sort()
ans = 0
l = set()
for x, y, c in p:
  if c == 0:
    l.add(y)
  else:
    t = -1
    for y_dash in l:
      if t < y_dash < y:
        t = y_dash
    if t != -1:
      ans += 1
      l.discard(t)
print(ans)