시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 9 3 3 37.500%

문제

지민이는 종이에 색칠하기를 좋아한다. 지민이는 W*H크기의 직사각형 종이를 가지고 있다. 지민이는 종이에 다음과 같이 색칠을 K번 하려고 한다. 0보다 크거나 같고, K-1보다 작거나 같은 i에 대해서, 다음과 같은 행동을 한 번씩 한다.

1. 종이를 x=f[i]에 맞춰서 접는다. 이 때, 왼쪽 종이가 오른쪽 종이 위에 올라오게 접는다.

2. 종이를 가로로 c[i]+1개의 크기가 동일 한 구간으로 나눈다. 그 다음에 c[i]번 가장 위의 구간부터 차례대로 접는다.

3. 왼쪽 아래가 (x1[i], y1[i]) 이고, 오른쪽 위가 (x2[i], y2[i])인 직사각형을 찾는다. 이 때, (0, 0)은 현재 접힌 상태에서 가장 왼쪽 아래 점이다. 그 직사각형을 칠한다. 이 때, 페인트는 겹쳐있는 모든 곳에 스며든다.

4. 종이를 편다.

예제는 1117번 문제를 참고한다.

W, H K, 그리고 각각의 i(0<=i<K)에 대해 f[i], c[i], x1[i], y1[i], x2[i], y2[i]가 주어질 때, 색칠되어 있지 않은 면적을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 W H K가 주어진다. W와 H는 10^9보다 작거나 같은 자연수이고, K는 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각각 접고 색칠하는 정보가 주어진다. f[i] c[i] x1[i] y1[i] x2[i] y2[i]가 주어진다. F[i]는 0보다 크거나 같고, W보다 작거나 같은 정수, c[i]는 1000보다 작거나 같은 정수 또는 0이다. C[i]+1은 H의 약수이고,  0<=x1[i]<x2[i]< max(f[i],W-f[i]), 0<=y1[i]<y2[i]<=H/(c[i]+1)이다.

출력

첫째 줄에 색칠되지 않은 영역의 넓이를 출력한다.

예제 입력

6 6 2
2 1 1 2 3 3
5 2 2 0 4 2

예제 출력

18

힌트

출처