실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
몇 차례의 혹독한 겨울을 견뎌낸 후, 범수는 그의 부동산 울타리를 다시 칠하기로 결정했습니다. 그의 부동산은 N개의 울타리로 둘러싸인 구역(1 <= N <= 50,000)으로 구성되어 있으며, 각각은 x축과 y축에 평행한 변을 가진 2차원 평면 상의 직사각형으로 표현됩니다. 구역들은 다른 구역 내에 포함될 수 있지만, 두 울타리가 겹치는 경우는 없으므로, 두 구역이 2차원 평면에서 동일한 영역을 차지한다면, 하나는 다른 하나 안에 포함되어 있어야 합니다.
범수는 다른 구역 안에 들어 있는 구역은 외부에서 볼 수 없다고 생각하여, 다른 구역 안에 포함되지 않은 구역만 다시 칠하려고 합니다. 범수가 칠해야 할 구역의 총 개수를 구해주십시오.
3 2 0 8 9 10 2 11 3 4 2 6 5
2
출처: USACO 2013 March Contest, Silver Problem 2. Farm Painting