레이팅 미적용농부 존은 멀티태스킹에 서투르다. 그는 자주 딴 데 정신이 팔려서 긴 작업을 끝마치기 어려워한다. 지금 그는 헛간의 한쪽 면을 칠하려 하고 있는데, 작은 직사각형 영역들을 칠하다가 소를 돌보는 일에 정신이 팔리기를 반복하는 바람에, 헛간의 어떤 부분은 다른 부분보다 페인트가 더 여러 겹 칠해진 상태가 되었다.
헛간의 한쪽 면을 2차원 \(x\)-\(y\) 평면으로 나타낼 수 있으며, 농부 존은 그 위에 \(N\)개의 직사각형을 칠한다. 각 직사각형은 변이 좌표축에 평행하며, 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표로 주어진다.
농부 존은 가까운 시일 내에 다시 칠할 필요가 없도록 헛간에 페인트를 여러 겹 칠하고 싶다. 하지만 지나치게 많은 겹을 칠하느라 시간을 낭비하고 싶지는 않다. 알고 보니 \(K\)겹의 페인트가 최적의 양이라고 한다. 존이 모든 직사각형을 칠한 후, 정확히 \(K\)겹의 페인트로 덮인 헛간의 넓이가 얼마인지 구하는 것을 도와주자.
문제 제공: Nick Wu
문제 제공: Nick Wu
첫째 줄에 \(N\)과 \(K\) (\(1 \leq K \leq N \leq 10^5\))가 주어진다. 남은 \(N\)개의 줄 각각에는 칠해지는 직사각형 영역을 나타내는 네 정수 \(x_1, y_1, x_2, y_2\)가 주어지며, 왼쪽 아래 꼭짓점은 \((x_1, y_1)\), 오른쪽 위 꼭짓점은 \((x_2, y_2)\)이다. 모든 \(x\)와 \(y\) 값은 \(0 \ldots 1000\) 범위이며, 모든 직사각형은 양의 넓이를 가진다.
정확히 \(K\)겹의 페인트로 덮인 헛간의 넓이를 출력한다.
paintbarn.in · 출력을 쓸 파일 paintbarn.out3 2
1 1 5 5
4 4 7 6
3 3 8 78riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > February > Silver