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 = []
for i in range(n):
    reds.append(tuple(map(int, input().split())))
reds = sorted(reds, key=lambda tup: tup[1], reverse=True)

blues = []
for i in range(n):
    blues.append(tuple(map(int, input().split())))
blues = sorted(blues, key=lambda tup: tup[0])

count = 0
for b in blues:
    paired = None
    for r in reds:
        if b[0] > r[0] and b[1] > r[1]:
            paired = r
            break
            
    if paired is not None:
        reds.remove(paired)
        count += 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
reds = []
for i in range(n):
    reds.append(tuple(map(int, input().split())))
reds = sorted(reds, key=lambda tup: tup[1], reverse=True)

blues = []
for i in range(n):
    blues.append(tuple(map(int, input().split())))
blues = sorted(blues, key=lambda tup: tup[0])

count = 0
for b in blues:
    paired = None
    for i in range(len(reds)):
        r = reds[i]
        if b[0] > r[0] and b[1] > r[1]:
            paired = i
            break
            
    if paired is not None:
        del reds[paired]
        count += 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
reds = []
for i in range(n):
    reds.append(tuple(map(int, input().split())))
reds = sorted(reds, key=lambda tup: tup[1], reverse=True)
#print(reds)

blues = []
for i in range(n):
    blues.append(tuple(map(int, input().split())))
#print(blues)
blues = sorted(blues, key=lambda tup: tup[0])
#print(blues)

count = 0
for b in blues:
    tmp = []
#    print(len(reds))
    for i in range(len(reds)):
        r = reds[i]
        if b[0] > r[0] and b[1] > r[1]:
            tmp.append(i)
            break
            
    if len(tmp) > 0:
        del reds[tmp[0]]
        count += 1

print(count)

Submission status: Accepted

Solution code:
n=int(input())
a=sorted([list(map(int,input().split())) for i in range(n)])
b=sorted([list(map(int,input().split())) for i in range(n)])
ans=0
for i in range(n):
    flag=0
    res=float("inf")
    for j in range(len(a)): #一番もっともなのを探す
        if b[i][0]>a[j][0]:
            if 0<b[i][1]-a[j][1]<res:
                res=b[i][1]-a[j][1]
                ind=j
                flag=1
    if flag:
        a.pop(ind)
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input().rstrip())
red = []
for i in range(N):
    a, b = input().rstrip().split()
    red.append((int(a), int(b)))
red.sort(key=lambda y: y[1], reverse=True)
blue = []
for i in range(N):
    a, b = input().rstrip().split()
    blue.append((int(a), int(b)))
blue.sort(key=lambda x: x[0])

# print(red, blue)

i = 0
while len(blue) > i:
    for j in red:
        if j[0] < blue[i][0] and j[1] < blue[i][1]:
            del blue[i]
            red.remove(j)
            break
    else:
        i += 1
    # print(red, blue)

print(N - len(red))

Submission status: Accepted

Solution code:
N=int(raw_input())
ab=[]
cd=[]
for i in xrange(N):
 ab.append(map(int,raw_input().split()))
for i in xrange(N):
 cd.append(map(int,raw_input().split()))
ab.sort(key=lambda x:x[1],reverse=True)
cd.sort()
for c,d in cd:
 for a,b in ab:
  if a<c and b<d:
   ab.remove([a,b])
   break
print N-len(ab)

Submission status: Accepted

Solution code:
N = int(input())
red = []
blue = []
for i in range(N):
    red.append(list(map(int, input().split())))
for j in range(N):
    blue.append(list(map(int, input().split())))

blue2 = sorted(blue, key=lambda x: x[0])
count = 0
for k in blue2:
    temp = -1
    pop = -1
    num = -1
    for l in red:
        num += 1
        if l[1] < k[1] and l[0] < k[0]:
            if l[1] > temp:
                temp = l[1]
                pop = num
    if temp >= 0:
        red.pop(pop)
        count += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())

red_points = [[int(i) for i in input().split()] for j in range(N)]

blue_points = [[int(i) for i in input().split()] for j in range(N)]

red_points.sort()
blue_points.sort()
count = 0
distance = 9999
for blue_point in blue_points:
    tmp = [i for i in red_points if blue_point[0] > i[0] and blue_point[1] > i[1]]
    if tmp:
        for j in tmp:
            if (blue_point[1] - j[1]) < distance:
                distance = blue_point[1] - j[1]
                min_red = j
        count = count + 1
        red_points.remove(min_red)
        distance = 9999

print(count)

Submission status: Accepted

Solution code:
n=int(input())
red=[]
blue=[]
for i in range(n):
    red.append(tuple(map(int,input().split())))
for i in range(n):
    blue.append(tuple(map(int,input().split())))
red=sorted(red,key=lambda x:-x[1])
blue=sorted(blue)
count=0
i=0

while i<len(blue):
    for j in range(len(red)):
        if red[j][0]<blue[i][0] and red[j][1]<blue[i][1]:
            count+=1
            del red[j]
            del blue[i]
            break
    else:
        i+=1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
red, blue = [], []
for _ in range(N):
    red.append(tuple(int(i) for i in input().split()))
for _ in range(N):
    blue.append(tuple(int(i) for i in input().split()))
ans = 0

red.sort(reverse=True,key=lambda x: x[0])
blue.sort(key=lambda x: x[1])

for bl in blue:
    for re in red:
        if re[0] < bl[0] and re[1] < bl[1]:
            ans += 1
            red.remove(re)
            break

print(ans)

Submission status: Accepted

Solution code:
GI = lambda: int(input()); GIS = lambda: map(int, input().split()); LGIS = lambda: list(GIS())

def main():
  N = GI()

  l = []

  for color in 'r', 'b':
    for _ in range(N):
      x, y = GIS()
      l.append((x, y, color))

  l.sort()
  rys = [0] * 200
  count = 0
  for x, y, c in l:
    if c == 'r':
      rys[y] = 1
    else:
      found = None
      for i in range(y):
        if rys[i]:
          found = i
      if found is not None:
        rys[found] = 0
        count += 1

  print(count)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - 2D Plane 2N Points
https://beta.atcoder.jp/contests/abc091/tasks/arc092_a

"""
import sys
from sys import stdin
from collections import namedtuple, deque
input = stdin.readline


edge = namedtuple('edge', ['to', 'cap', 'rev'])

def add_edge(G, f, t, c):
    G[f].append(edge(t, c, len(G[t])))
    G[t].append(edge(f, 0, len(G[f]) - 1))


def bfs(G, level, s):
    for i in range(len(level)):
        level[i] = -1
    que = deque()
    level[s] = 0
    que.append(s)
    while que:
        v = que.popleft()
        for e in G[v]:
            if e.cap > 0 and level[e.to] < 0:
                level[e.to] = level[v] + 1
                que.append(e.to)


def dfs(G, iter, level, v, t, f):
    if v == t:
        return f
    for i in range(iter[v], len(G[v])):
        e = G[v][i]
        if e.cap > 0 and level[v] < level[e.to]:
            d = dfs(G, iter, level, e.to, t, min(f, e.cap))
            if d > 0:
                G[v][i] = edge(e.to, e.cap - d, e.rev)
                G[e.to][e.rev] = edge(G[e.to][e.rev].to, G[e.to][e.rev].cap + d, G[e.to][e.rev].rev)
                return d
    return 0


def max_flow(G, V, s, t):
    level = [0] * V
    flow = 0
    while True:
        bfs(G, level, s)
        if level[t] < 0:
            return flow
        iter = [0] * V
        while True:
            f = dfs(G, iter, level, s, t, float('inf'))
            if f > 0:
                flow += f
            else:
                break


def main(args):
    """
    - 追加したソースノードID: 0
    - 赤い点ID: 1〜N
    - 青い点ID: N+1 〜2N
    - 追加したシンクノードID: 2N + 1(2N + 2 - 1)
    として、ノード0 → 2N+1 への最大流を求める
    """
    N = int(input())
    G = [[] for _ in range(N*2 + 2)]
    red_points = []
    for ri in range(1, N+1):
        rx, ry = map(int, input().split())
        red_points.append([rx, ry])
        add_edge(G, 0, ri, 1)   #  ソースノードは全ての赤い点と繋ぐ

    for bi in range(1, N+1):
        bx, by = map(int, input().split())
        add_edge(G, bi+N, N*2+1, 1) #  全ての青い点はシンクノードに繋ぐ
        for i, r in enumerate(red_points, start=1):
            rx = r[0]
            ry = r[1]
            if rx < bx and ry < by:
                add_edge(G, i, bi+N, 1) #  仲良しペアを作ることができるので辺を作成

    ans = max_flow(G, 2*N+2, 0, 2*N+1) #  ソースとシンク間の最大流
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N = int(input())
a = []
b = []
for i in range(N):
    a.append(list(map(int, input().split())))
for i in range(N):
    b.append(list(map(int, input().split())))
a_sorted = sorted(a, key = lambda x:-x[1])
b_sorted = sorted(b)

ans = 0
for i in range(len(b_sorted)):
    for j in range(len(a_sorted)):
        if(b_sorted[i][0] > a_sorted[j][0] and b_sorted[i][1] > a_sorted[j][1]):
            ans += 1
            a_sorted.pop(j)
            break
print(ans)

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

AB_used = set()
CD_used = set()
for index_ab, ab in enumerate(AB):
    mx = float('inf')
    my = float('inf')
    i = -1
    j = -1
    if index_ab in AB_used:
        continue
    for index_cd, cd in enumerate(CD):
        if index_cd in CD_used:
            continue
        if (ab[0] < cd[0]) & (ab[1] < cd[1]) & (cd[1] < my) & (cd[0] < mx):
            i, j = index_ab, index_cd
            my = cd[1]
    if (i != -1) & (j != -1):
        AB_used.add(i)
        CD_used.add(j)

print(len(AB_used))

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

AB_used = set()
CD_used = set()
for index_ab, ab in enumerate(AB):
    my = float('inf')
    i = -1
    j = -1
    if index_ab in AB_used:
        continue
    for index_cd, cd in enumerate(CD):
        if index_cd in CD_used:
            continue
        if (ab[0] < cd[0]) & (ab[1] < cd[1]) & (cd[1] < my):
            i, j = index_ab, index_cd
            my = cd[1]
    if (i != -1) & (j != -1):
        AB_used.add(i)
        CD_used.add(j)

print(len(AB_used))

Submission status: Accepted

Solution code:
class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    # def __repr__(self):
    #     return '({}, {})'.format(self.x, self.y)

    # def __str__(self):
    #     return '({}, {})'.format(self.x, self.y)


def prepare_points(N, color_str):
    points = []
    for i in range(N):
        tmp = input().split()
        x, y = int(tmp[0]), int(tmp[1])
        point = Point(x, y)
        points.append((point, color_str))
    return points


def main():
    N = int(input())
    red_points = prepare_points(N, 'r')
    blue_points = prepare_points(N, 'b')
    sorted_ = sorted((red_points + blue_points), key=lambda x: x[0].x)
    uses = set()
    count = 0
    for item in sorted_:
        if item[1] == 'r':
            uses.add(item)
        else:
            reds = {
                foo
                for foo in uses if foo[1] == 'r' and foo[0].y < item[0].y
            }
            # print(item, reds)
            if not reds:
                continue
            max_p = max(reds, key=lambda x: x[0].y)
            if max_p[0].y < item[0].y:
                uses.remove(max_p)
                count += 1
    # print(sorted_)
    # print(uses)
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# AtCoder Beginner Contest
# Problem C


def get_candidate_points(sorted_a_b: list, c: int, d: int) -> list:
    candidate_a_b = [x for x in sorted_a_b if (x[0] < c) and (x[1] < d)]
    return sorted(candidate_a_b, key=lambda x: (x[1], x[0]), reverse=True)


if __name__ == '__main__':
    number = int(input())

    a_b = [list(map(int, input().split())) for _ in range(number)]
    c_d = [list(map(int, input().split())) for _ in range(number)]
    sorted_a_b = sorted(a_b, key=lambda x: (x[0], x[1]))
    sorted_c_d = sorted(c_d, key=lambda y: (y[0], y[1]))
    count = 0

    for c, d in sorted_c_d:
        points = get_candidate_points(sorted_a_b, c, d)

        if len(points) >= 1:
            sorted_a_b.remove(points[0])
            count += 1

    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2435165
#AOJ最大流プログラム
#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

import collections
class Dinic:

    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]

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

    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])

    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level

    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO


#今回の問題分（インプット、頂点の組）FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

n=int(input())
s=[]
ss=[]
for i in range(n):
    s.append([int(i) for i in input().split()])
    
for i in range(n):
    ss.append([int(i) for i in input().split()])

pair=[]
for i in range(len(s)):
    right=[]
    for j in range(n):    
        if s[j][0]<ss[i][0] and s[j][1]<ss[i][1]:
            right.append(j)
    pair.append(right)

#print(pair)

#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO


#頂点の組u,vと辺の重みc（今回は1）からグラフ作って最大流で解くFOOOOOOOOOOOOOOOOO

V=len(pair)+n+2 #(sとt追加)

dinic = Dinic(V)

for i in range(len(pair)): #始点s（番号0）から青い点(1から最大len(pair))への辺
    u, v, c = 0, i+1, 1
    dinic.add_edge(u, v, c)
            
for i in range(n): #　赤い点（len(pair)+1から最大len(pair)+n）から終点t（番号V-1）への辺
    u, v, c = i+len(pair)+1, V-1, 1
    dinic.add_edge(u, v, c)    
    
for i in range(len(pair)): #青い点（番号1から最大len(pair)に振り直し）から　赤い点（番号1～100に振り直し）への辺
    for j in range(len(pair[i])):
        node1, node2 = i+1,pair[i][j]+len(pair)+1
        
        u, v, c = node1, node2, 1
        dinic.add_edge(u, v, c)
        
print (dinic.max_flow(0, V-1))     

#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO


"""
元々のinput
V, E =  [int(i) for i in input().split()]

dinic = Dinic(V)

for i in range(E):
    u, v, c = [int(i) for i in input().split()]
    dinic.add_edge(u, v, c)

print (dinic.max_flow(0, V-1))
"""

Submission status: Accepted

Solution code:
#coding=utf-8

def solve(abs, cds):
    abs = sorted(abs, key = lambda x: -1 * x[1]) #sorted by y
    cds = sorted(cds, key = lambda x: x[0]) #sorted by x 

    count = 0
    for r in cds:
        _abs = list(filter(lambda x: r[0] > x[0] and r[1] > x[1], abs))
        if len(_abs) == 0:
            continue
        del abs[abs.index(_abs[0])]
        count += 1
    return count

if __name__ == '__main__':
    N = int(input())
    abs = []
    cds = []
    for _ in range(N):
        abs = abs + [list(map(lambda x: int(x), input().split()))] 
    for _ in range(N):
        cds = cds + [list(map(lambda x: int(x), input().split()))] 

    print(solve(abs, cds))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - 2D Plane 2N Points
https://beta.atcoder.jp/contests/abc091/tasks/arc092_a

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline
edge = namedtuple('edge', ['to', 'cap', 'rev'])


def add_edge(G, f, t, c):
    G[f].append(edge(t, c, len(G[t])))
    G[t].append(edge(f, 0, len(G[f]) - 1))


def dfs(G, used, v, t, f):
    if v == t:
        return f
    used[v] = True
    for i in range(len(G[v])):
        e = G[v][i]
        if (not used[e.to]) and (e.cap > 0):
            d = dfs(G, used, e.to, t, min(f, e.cap))
            if d > 0:
                G[v][i] = edge(e.to, e.cap - d, e.rev)
                G[e.to][e.rev] = edge(G[e.to][e.rev].to, G[e.to][e.rev].cap + d, G[e.to][e.rev].rev)
                return d
    return 0


def max_flow(G, V, s, t):
    used = [False] * V
    flow = 0
    while True:
        for i in range(len(used)):
            used[i] = False
        f = dfs(G, used, s, t, float('inf'))
        if f == 0:
            return flow
        flow += f


def main(args):
    N = int(input())
    G = [[] for _ in range(N*2 + 2)]
    red_points = []
    for ri in range(1, N+1):
        rx, ry = map(int, input().split())
        red_points.append([rx, ry])
        add_edge(G, 0, ri, 1)

    for bi in range(1, N+1):
        bx, by = map(int, input().split())
        add_edge(G, bi+N, N*2+1, 1)
        for i, r in enumerate(red_points, start=1):
            rx = r[0]
            ry = r[1]
            if rx < bx and ry < by:
                add_edge(G, i, bi+N, 1)

    ans = max_flow(G, 2*N+2, 0, 2*N+1)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
#abc091c

N=int(raw_input())
ab=[]
cd=[]
for i in xrange(N):
 ab.append(map(int,raw_input().split()))
for i in xrange(N):
 cd.append(map(int,raw_input().split()))
ab.sort(key=lambda x:x[1],reverse=True)
cd.sort()
for c,d in cd:
 for a,b in ab:
  if a<c and b<d:
   ab.remove([a,b])
   break
print N-len(ab)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]
for i in range(n):
    a.append(list(map(int,input().split())))
for i in range(n):
    b.append(list(map(int,input().split())))
an=sorted(a, key=lambda x:-x[1])
bn=sorted(b)

count=0
for i in range(len(bn)):
    for j in range(len(an)):
        
        if bn[i][0]>an[j][0] and bn[i][1]>an[j][1]:
            count+=1
            an.pop(j)
            break
 
print(count)

Submission status: Accepted

Solution code:

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

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

c = 0
for bx, by in blue:
    for i, (rx, ry) in enumerate(red):
        if rx<bx and ry<by:
            c += 1
            red.pop(i)
            break

print(c)

Submission status: Accepted

Solution code:
red_p = []
blue_p = []
count = 0
n = int(input())
for i in range(n):
    a_ad, b_ad = map(int, input().split())
    red_p.append((a_ad, b_ad))
for i in range(n):
    c_ad, d_ad = map(int, input().split())
    blue_p.append((c_ad, d_ad))
red_p.sort(key = lambda x: x[1], reverse = True)
blue_p.sort()
for i in range(n):
    l = len(red_p)
    for k in range(l):
        if red_p[k][1] < blue_p[i][1] and red_p[k][0] < blue_p[i][0]:
            count += 1
            red_p = red_p[:k] + red_p[k+1:]
            break
print(count)

Submission status: Accepted

Solution code:
#https://abc010.contest.atcoder.jp/tasks/abc010_4
#http://kmjp.hatenablog.jp/entry/2014/06/08/0900

#よくわからない最大フロー用のdfs---------------------------------

num=201 #今回のnの最大値100*2+1

def dfs(cur):
	global vis
	global EE
	vis[cur] = 1

	if cur==num:
		return 1

	for i in range(num+1):
		if vis[i]==0 and EE[cur][i]>0 and dfs(i) > 0:
			EE[cur][i] -= 1
			EE[i][cur] += 1
			return 1
	return 0
#--------------------------------------------------------------

#今回の問題分（インプット～隣接リストの作成）------------------

n=int(input())
s=[]
ss=[]
for i in range(n):
    s.append([int(i) for i in input().split()])
for i in range(n):
    ss.append([int(i) for i in input().split()])
#s.sort(key=lambda x:(x[0],x[1]))
#ss.sort(key=lambda x:(x[0],x[1]))

pair=[]
for i in range(len(s)):
    right=[]
    for j in range(n):    
        if s[j][0]<ss[i][0] and s[j][1]<ss[i][1]:
            right.append(j)
    pair.append(right)
#pair.sort(key=lambda x:len(x))

#print(pair)

#------------------------------------------------------------

#BFSにぶち込む用のグラフ作成---------------------------------

EE = [[0 for x in range(num+1)] for y in range(num+11)]
vis = [0] * (num+1)

for i in range(len(pair)): #1から最大100　始点s（番号0）から青い点への辺
	EE[0][i+1] = 1
#	EE[i+1][0] = 1

for i in range(n): #101から最大200　赤い点から終点t（番号201）への辺
	EE[i+101][num] = 1

for i in range(len(pair)): #青い点（番号1～100に振り直し）から　赤い点（番号101～200）への辺
    for j in range(len(pair[i])):
        node1, node2 = i+1,pair[i][j]+101
#        EE[node1][node2] = EE[node2][node1] = 1　なんでこれダメなんだろう
        EE[node1][node2] = 1

#風呂～～--------------------------------------------------

flow=0
while 1:
    for i in range(0, num+1):
        vis[i] = 0
    if dfs(0) == 0:
        break
    flow += 1

print (flow)

#----------------------------------------------------------

Submission status: Accepted

Solution code:
#https://abc010.contest.atcoder.jp/tasks/abc010_4
#http://kmjp.hatenablog.jp/entry/2014/06/08/0900

#よくわからない最大フロー用のdfs---------------------------------

num=201 #今回のnの最大値100*2+1

def dfs(cur):
	global vis
	global EE
	vis[cur] = 1

	if cur==num:
		return 1

	for i in range(num+1):
		if vis[i]==0 and EE[cur][i]>0 and dfs(i) > 0:
			EE[cur][i] -= 1
			EE[i][cur] += 1
			return 1
	return 0
#--------------------------------------------------------------

#今回の問題分（インプット～隣接リストの作成）------------------

n=int(input())
s=[]
ss=[]
for i in range(n):
    s.append([int(i) for i in input().split()])
for i in range(n):
    ss.append([int(i) for i in input().split()])
#s.sort(key=lambda x:(x[0],x[1]))
#ss.sort(key=lambda x:(x[0],x[1]))

pair=[]
for i in range(len(s)):
    right=[]
    for j in range(n):    
        if s[j][0]<ss[i][0] and s[j][1]<ss[i][1]:
            right.append(j)
    pair.append(right)
#pair.sort(key=lambda x:len(x))

#print(pair)

#------------------------------------------------------------

#BFSにぶち込む用のグラフ作成---------------------------------

EE = [[0 for x in range(num+1)] for y in range(num+11)]
vis = [0] * (num+1)

for i in range(len(pair)): #1から最大100　始点s（番号0）から青い点への辺
	EE[0][i+1] = 1
	EE[i+1][0] = 1

for i in range(n): #101から最大200　赤い点から終点t（番号201）への辺
	EE[i+101][num] = 1

for i in range(len(pair)): #青い点（番号1～100に振り直し）から　赤い点（番号101～200）への辺
    for j in range(len(pair[i])):
        node1, node2 = i+1,pair[i][j]+101
#        EE[node1][node2] = EE[node2][node1] = 1　なんでこれダメなんだろう
        EE[node1][node2] = 1

#風呂～～--------------------------------------------------

flow=0
while 1:
    for i in range(0, num+1):
        vis[i] = 0
    if dfs(0) == 0:
        break
    flow += 1

print (flow)

#----------------------------------------------------------

Submission status: Accepted

Solution code:
#https://abc010.contest.atcoder.jp/tasks/abc010_4
#http://kmjp.hatenablog.jp/entry/2014/06/08/0900

#よくわからない最大フロー用のdfs---------------------------------

num=201 #今回のnの最大値100*2+1

def dfs(cur):
	global vis
	global EE
	vis[cur] = 1

	if cur==num:
		return 1

	for i in range(num+1):
		if vis[i]==0 and EE[cur][i]>0 and dfs(i) > 0:
			EE[cur][i] -= 1
			EE[i][cur] += 1
			return 1
	return 0
#------------------------------------------------------------------------------------

#今回の問題分（インプット～隣接リストの作成）------------------

n=int(input())
s=[]
ss=[]
for i in range(n):
    s.append([int(i) for i in input().split()])
for i in range(n):
    ss.append([int(i) for i in input().split()])
s.sort(key=lambda x:(x[0],x[1]))
ss.sort(key=lambda x:(x[0],x[1]))

pair=[]
for i in range(len(s)):
    right=[]
    for j in range(n):    
        if s[j][0]<ss[i][0] and s[j][1]<ss[i][1]:
            right.append(j)
    pair.append(right)
pair.sort(key=lambda x:len(x))

#print(pair)

#------------------------------------------------------------------------------------

#BFSにぶち込む用のグラフ作成------------------------------------------

EE = [[0 for x in range(num+1)] for y in range(num+11)]
vis = [0] * (num+1)

for i in range(len(pair)): #1から最大100　始点s（番号0）から青い点への辺
	EE[0][i+1] = 1
	EE[i+1][0] = 1

for i in range(n): #101から最大200　赤い点から終点t（番号201）への辺
	EE[i+101][num] = 1

for i in range(len(pair)): #青い点（番号1～100に振り直し）から　赤い点（番号101～200）への辺
    for j in range(len(pair[i])):
        node1, node2 = i+1,pair[i][j]+101
#        EE[node1][node2] = EE[node2][node1] = 1　なんでこれダメなんだろう
        EE[node1][node2] = 1

#風呂～～-----------------------------------------------------------------------

flow=0
while 1:
    for i in range(0, num+1):
        vis[i] = 0
    if dfs(0) == 0:
        break
    flow += 1

print (flow)

#------------------------------------------------------------------------------------

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]
for i in range(n):
    a.append(list(map(int,input().split())))
for i in range(n):
    b.append(list(map(int,input().split())))
an=sorted(a, key=lambda x:-x[1])
bn=sorted(b)#, key=lambda x:(x[0],x[1]))
count=0
for i in range(len(bn)):
    for j in range(len(an)):
#        print(an[j],bn[i])
        if bn[i][0]>an[j][0] and bn[i][1]>an[j][1]:
            count+=1
            an.pop(j)
            break
 
print(count)

Submission status: Accepted

Solution code:
N = int(input())
red = [3*N] * (2*N)
blue = [-1] * (2*N)
for i in range(N):
    a, b = (int(j) for j in input().split())
    red[a] = b
for i in range(N):
    a, b = (int(j) for j in input().split())
    blue[a] = b
ans = 0
for i in range(1, 2*N):
    for j in range(blue[i]-1, -1, -1):
        if j in red and red.index(j) < i:
            ans += 1
            blue[i] = 0
            red[red.index(j)] = 3 * N
            break
print(ans)

Submission status: Accepted

Solution code:
def friendly_pairs(red_points, blue_points):
    def can_be_friends(r, b):
        return r[0] < b[0] and r[1] < b[1]
    
    red = sorted(red_points, key=lambda x: (x[1], x[0]), reverse=True)
    blue = sorted(blue_points, key=lambda x: (x[0], x[1]))
    count = 0
    for b in blue:
        potential_friends = filter(lambda x: can_be_friends(x, b), red)
        if potential_friends:
            count += 1
            red.remove(potential_friends[0])
    return count


if __name__ == '__main__':
    n = int(raw_input())
    red_points = [map(int, raw_input().split())  for _ in xrange(n)]
    blue_points = [map(int, raw_input().split())  for _ in xrange(n)]
    print friendly_pairs(red_points, blue_points)

Submission status: Accepted

Solution code:
N = int(input())
R = []
for i in range(N):
    R.append(input().split())
    R[i].append(0)
R.sort(key=lambda x:(-int(x[1])))

B = []
for i in range(N):
    B.append(input().split())
    B[i].append(0)
B.sort(key=lambda x:(int(x[0]),int(x[1])))

a = 0
for i in range(N):
    for j in range(N):
        if int(R[j][0]) < int(B[i][0]) and int(R[j][1]) < int(B[i][1]) and R[j][2] == 0 and B[i][2] == 0:
            a += 1
            R[j][2] = j+1
            B[i][2] = j+1
            break

print(a)

Submission status: Accepted

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

cd = sorted(cd, key=lambda x:x[0])
ab = sorted(ab, key=lambda x:x[1],reverse=True)


count = 0
i = 0
while i < N:
    for j in range(len(ab)):
        if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1]:
            count += 1
            del ab[j]
            break
    i += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())

L = []
for _ in range(N):
    p = [int(n) for n in input().split()]
    L.append((p[0], p[1], 'R'))

for _ in range(N):
    p = [int(n) for n in input().split()]
    L.append((p[0], p[1], 'B'))

L.sort(key=lambda x: x[0])

S = set()
for x, y, c in L:
    if c == 'R':
        S.add((x, y))
    else:
        SL = list(S)
        SL.sort(key=lambda x: x[1], reverse=True)
        SL = [s for s in SL if s[1] < y]
        if len(SL) > 0:
            S.remove(SL[0])

print(N - len(S))

Submission status: Accepted

Solution code:
n = int(input())
red = [list(map(int, input().split())) for i in range(n)]
red.sort(key=lambda x:x[1], reverse=True)
blue = [list(map(int, input().split())) for i in range(n)]
blue = sorted(blue)
ans = 0
for x_b, y_b in blue:
  for x_r, y_r in red:
    if x_r < x_b and y_r < y_b:
      red.remove([x_r, y_r])
      ans += 1
      break
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
red = []
for _ in range(n):
    red.append(na())
blue = []
for _ in range(n):
    blue.append(na())

red.sort()
blue.sort()
ans = 0

tmp = []
for i in blue:
    for j in red:
        if i[0] > j[0] and i[1] > j[1]:
            tmp.append(j)
    if tmp != []:
        max_red = max(tmp, key=lambda x:x[1])
        ans += 1
        red.remove(max_red)
        tmp = []
    else:
        pass

print(ans)

Submission status: Accepted

Solution code:
#coding :utf-8
N = int(input())

aka = []
for i in range(N):
    aka.append(list(map(int, input().split())))


ao = []
for i in range(N):
    ao.append(list(map(int, input().split())))


memo = [0 for i in range(N)]
memoB = [0 for i in range(N)]

_aka = sorted(aka, key=lambda x: x[0])
_ao = sorted(ao, key=lambda x: x[0])
ans = 0
for j in range(N):
    _i = -1
    _y = -1
    for i in range(N): 
        if _ao[j][0] > _aka[i][0] and _ao[j][1] > _aka[i][1] and memo[i] == 0:
            if _y < _aka[i][1]:
                _y = _aka[i][1]
                _i = i
    if not _i == -1:
        ans += 1
        memo[_i] = 1
        

print(ans)