시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 312 | 129 | 113 | 42.481% |
상근이는 생일 선물로 구간 N개를 받았다. 여기서 말하는 구간이란 수의 구간이며, [A, B]와 같은 구간이다. 구간을 어떻게 선물로 받았는 지는 잘 모르겠지만, 진짜로 그 수학에 나오는 구간이다.
상근이는 자신이 가지고 있는 구간 중에서 아래와 같은 조건을 만족하는 가장 긴 서로 다른 구간의 수열을 찾으려고 한다.
수열에 포함되는 모든 구간은 다음 위치에 있는 구간을 포함해야 한다.
가장 긴 수열을 찾는 프로그램을 작성하시오.
첫째 줄에 구간의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
다음 N개 줄에는 각 구간 [A,B]의 정보 A와 B가 주어진다. (1 ≤ A < B ≤ 1,000,000)
첫째 줄에 수열의 길이 K를 출력한다. 다음 K줄에는 수열에 포함되는 구간을 입력 형식과 같이 한 줄에 하나씩 순서대로 출력한다.
5 10 30 20 40 30 50 10 60 30 40
3 10 60 30 50 30 40
3 3 4 2 5 1 6
3 1 6 2 5 3 4
6 1 4 1 5 1 6 1 7 2 5 3 5
5 1 7 1 6 1 5 2 5 3 5
Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #4 5번