시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB146650.000%

문제

지민이는 종이에 색칠하기를 좋아한다. 지민이는 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가 주어진다.

둘째 줄부터 N개의 줄에는 각각 접고 색칠하는 정보를 의미하는 6개의 정수 f[i], c[i], x1[i], y1[i], x2[i], y2[i]가 주어진다.

출력

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

제한

  • 1 ≤ W, H ≤ 109
  • 1 ≤ K ≤ 50
  • 0 ≤ f[i] ≤ W
  • 0 ≤ c[i] ≤ 1,000
  • c[i]+1은 H의 약수
  • 0 ≤ x1[i] < x2[i] ≤ max(f[i], W-f[i])
  • 0 ≤ y1[i] < y2[i] ≤ H/(c[i]+1)

예제 입력 1

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

예제 출력 1

18

예제 입력 2

5 6 1
2 2 1 1 3 2

예제 출력 2

21

예제 입력 3

2 4 2
0 1 0 1 2 2
0 0 0 1 1 4

예제 출력 3

3

예제 입력 4

21 30 5
3 4 4 2 7 5
21 14 0 0 19 2
7 9 2 1 6 2
11 5 5 2 11 4
13 4 9 3 12 5

예제 출력 4

27

예제 입력 5

30 42 5
16 5 3 0 14 2
24 1 1 1 22 15
25 6 5 0 12 1
21 13 8 0 18 1
4 20 9 1 13 2

예제 출력 5

336

예제 입력 6

26 60 5
17 4 9 1 13 3
17 1 1 3 4 14
24 11 20 0 23 1
4 0 18 45 19 46
21 2 7 12 13 14

예제 출력 6

1319

예제 입력 7

17 3 6
17 2 7 0 12 1
2 0 6 0 10 3
10 0 4 1 6 2
2 2 11 0 12 1
10 0 0 1 4 2
13 0 5 1 12 2

예제 출력 7

20

출처