Rectangles Too!

시간 제한3초메모리 제한128 MB

요약

각 사각형이 다음 사각형보다 왼쪽 아래에 놓이는 가장 긴 사슬의 길이를 구한다.

난이도: 어려움10점 중 8점
유형: 정렬, 동적 계획법, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

좌표평면 위의 직사각형은 왼쪽 아래 꼭짓점 $(x_1, y_1)$ 과 오른쪽 위 꼭짓점 $(x_2, y_2)$ 로 주어지며, $x_1 \le x_2$ 이고 $y_1 \le y_2$ 이다.

두 직사각형 $A = ((x_1^A, y_1^A), (x_2^A, y_2^A))$ 와 $B = ((x_1^B, y_1^B), (x_2^B, y_2^B))$ 에 대해, 다음 두 조건이 모두 성립하면 $A$ 가 $B$ 에 선행한다고 하고 $A \preceq B$ 로 쓴다.

$x_2^A < x_1^B \quad\text{그리고}\quad y_2^A < y_1^B.$

평면 위에 놓인 직사각형들의 모임이 주어진다. 이 모임에서

$A_1 \preceq A_2 \preceq \cdots \preceq A_L$

을 만족하는 가장 긴 직사각형 수열 $(A_1, A_2, \ldots, A_L)$ 의 길이 $L$ 을 구하여라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 직사각형의 개수를 나타내는 정수 $n$ ( $1 \le n \le 100000$ )이 주어진다. 이어지는 $n$ 개의 줄에는 각각 네 정수 $x_1\ y_1\ x_2\ y_2$ ( $-1000000 \le x_1 \le x_2 \le 1000000$ , $-1000000 \le y_1 \le y_2 \le 1000000$ )가 주어지며, 이는 한 직사각형의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점을 나타낸다. 입력의 끝은 정수 $0$ 하나만 있는 줄로 표시된다.

출력

각 테스트 케이스마다 가장 긴 직사각형 사슬의 길이를 정수 하나로 한 줄에 출력한다.

예제2

예제 1

입력

3
1 5 2 8
3 -1 5 4
10 10 20 20
2
2 1 4 5
6 5 8 10
0

예상 출력

2
1

예제 2
입력
```
1
0 0 1 1
0
```
예상 출력
```
1
```