로봇 쟁기

면접 대비

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

요약

크기가 최대 240×240인 격자 위에 최대 200개의 축에 나란한 직사각형이 주어질 때, 적어도 하나의 직사각형에 포함되는 단위 정사각형의 개수를 센다.

난이도: 쉬움10점 중 3점
유형: 구현, 시뮬레이션, 배열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

농부 존은 밭을 하나하나 끝없이 가는 고된 일에서 벗어나기 위해 새 로봇 쟁기를 구입했다. 이 쟁기는 목적을 잘 이루지만 한 가지 제약이 있다. 로봇 쟁기는 변의 길이가 정수인 완전한 직사각형 영역만 갈 수 있다.

존의 밭에는 나무와 여러 장애물이 있어서, 그는 쟁기에게 서로 겹칠 수도 있는 여러 직사각형을 갈도록 지시한다. 그는 여러 쟁기질 지시를 준 뒤 실제로 갈린 칸이 몇 개인지 궁금하다. 각 지시는 갈아야 할 직사각형을 그 왼쪽 아래와 오른쪽 위의 $x$ , $y$ 좌표로 나타낸다.

밭은 $x$ 축과 $y$ 축에 평행한 변을 가진 정사각형 칸들로 나뉜다. 밭의 너비는 $X$ 칸, 높이는 $Y$ 칸이다 ( $1 \le X \le 240$ ; $1 \le Y \le 240$ ). $I$ 개의 지시 ( $1 \le I \le 200$ )는 각각 네 정수 $X_{ll}$ , $Y_{ll}$ , $X_{ur}$ , $Y_{ur}$ 로 이루어진다 ( $1 \le X_{ll} \le X_{ur} \le X$ ; $1 \le Y_{ll} \le Y_{ur} \le Y$ ). 이는 갈아야 할 직사각형의 왼쪽 아래와 오른쪽 위 좌표이다. 쟁기는 범위 $(X_{ll} \dots X_{ur},\ Y_{ll} \dots Y_{ur})$ 에 속한 모든 칸을 가는데, 양 끝의 열과 행에 해당하는 칸까지 모두 포함된다.

너비 6칸, 높이 4칸인 밭을 생각해 보자. 존이 아래와 같이 두 개의 쟁기질 지시를 내리면, 밭은 '*'와 '#'로 표시된 것처럼 갈린다 (이미 갈린 칸은 모두 똑같아 보이지만, '#'는 가장 최근에 갈린 칸을 나타낸다):

    ......             **....             #####.
    ......  (1,1)(2,4) **....  (1,3)(5,4) #####.
    ......             **....             **....
    ......             **....             **....

모두 합쳐 14개의 칸이 갈렸다.

입력

첫째 줄: 공백으로 구분된 세 정수 $X$ , $Y$ , $I$
둘째 줄부터 $I+1$ 째 줄까지: $i+1$ 째 줄에는 $i$ 번째 쟁기질 지시가 담기며, 네 정수 $X_{ll}$ , $Y_{ll}$ , $X_{ur}$ , $Y_{ur}$ 로 기술된다

출력

첫째 줄: 갈린 칸의 총 개수를 나타내는 정수 하나

예제3

예제 1
입력
```
6 4 2
1 1 2 4
1 3 5 4
```
예상 출력
```
14
```
예제 2
입력
```
1 1 1
1 1 1 1
```
예상 출력
```
1
```
예제 3
입력
```
10 10 2
1 1 2 2
5 5 6 6
```
예상 출력
```
8
```