코끼리
시간 제한3초메모리 제한128 MB
N개의 서로 다른 좌표점이 주어질 때 x, y 모두 증가하는 최장 부분열의 길이와 그런 최장 부분열의 개수를 1,000,000,007로 나눈 나머지로 구합니다.
문제
정수 좌표평면으로 나타낸 호수에 N개의 식물이 떠 있고, 각 식물은 서로 다른 정수 좌표에 있다.
매일 아침 코끼리는 식물들 사이를 점프하며 운동한다. 코끼리는 현재 식물보다 x좌표와 y좌표가 모두 큰 식물로만 점프할 수 있다. 즉, (x1, y1)에 있는 식물에서 (x2, y2)에 있는 식물로 이동하려면 x2 > x1이고 y2 > y1이어야 한다. 코끼리는 아무 식물에서나 운동을 시작할 수 있다.
모든 식물의 좌표가 주어졌을 때, 코끼리가 방문할 수 있는 식물 수의 최댓값을 구하라. 또한 그 최댓값을 달성하는 점프 순서의 개수를 구하라. 개수가 매우 클 수 있으므로 1 000 000 007로 나눈 나머지를 출력한다.
입력
첫째 줄에 식물의 수 N이 주어진다. (1 <= N <= 300 000)
다음 N개의 줄에는 각 식물의 좌표 xi, yi가 주어진다. (0 <= xi, yi <= 1 000 000 000)
두 식물이 같은 좌표에 있는 경우는 없다.
출력
첫째 줄에 코끼리가 방문할 수 있는 식물 수의 최댓값을 출력한다.
둘째 줄에 그 최댓값을 달성하는 점프 순서의 개수를 1 000 000 007로 나눈 나머지를 출력한다.