RiseOJ – 소는 왜 길을 건넜을까

설명

농부 존의 소들은 길을 효과적으로 건너는 법을 배우려 하고 있다. 옛날의 "닭은 왜 길을 건넜을까?" 농담을 떠올린 소들은 닭이 길 건너기의 전문가임에 틀림없다고 생각하고, 도움을 줄 닭을 찾아 나선다.

알고 보니 닭은 매우 바쁜 동물이라 소를 도울 시간이 한정되어 있다. 농장에는 $$C$$ 마리의 닭이 있으며 ( $1 \leq C \leq 20,000$ ), 편의상 $1 \ldots C$ 번으로 번호가 매겨져 있고, 각 닭 $$i$$ 는 정확히 시각 $$T_i$$ 에만 소를 도울 의향이 있다. 소들은 결코 서두르는 법이 없어 일정에 더 여유가 있다. 농장에는 $$N$$ 마리의 소가 있으며 ( $1 \leq N \leq 20,000$ ), 편의상 $1 \ldots N$ 번으로 번호가 매겨져 있고, 소 $$j$$ 는 시각 $$A_j$$ 부터 시각 $$B_j$$ 사이에 길을 건널 수 있다. "짝꿍 시스템"이 최선의 방법이라고 생각한 각 소 $$j$$ 는 자신이 길을 건너는 것을 도와줄 닭 $$i$$ 를 찾고 싶어 한다. 둘의 일정이 맞으려면 $$i$$ 와 $$j$$ 는 $A_j \leq T_i \leq B_j$ 를 만족해야 한다.

각 소는 최대 한 마리의 닭과, 각 닭은 최대 한 마리의 소와 짝지어질 수 있을 때, 만들 수 있는 소-닭 쌍의 최대 개수를 계산하시오.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 $$C$$ 와 $$N$$ 이 주어진다. 다음 $$C$$ 개의 줄에 $T_1 \ldots T_C$ 가 주어지고, 다음 $$N$$ 개의 줄에 $j = 1 \ldots N$ 에 대한 $$A_j$$ 와 $$B_j$$ ( $A_j \leq B_j$ )가 주어진다. $$A$$ , $$B$$ , $$T$$ 는 모두 1,000,000,000 이하의 음이 아닌 정수이다(서로 다르지 않을 수도 있다).

출력 형식

가능한 소-닭 쌍의 최대 개수를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 helpcross.in · 출력을 쓸 파일 helpcross.out

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Silver

올림피아드 > USACO > 2016-2017 > February > Silver

태그

JudgeUSACO

소는 왜 길을 건넜을까

평가 및 의견

풀이 제출