접힌 종이 색칠하기

W 곱하기 H 직사각형을 세로선과 여러 번의 가로 접기로 K번 접고, 각 회차마다 직사각형 하나를 모든 겹에 칠한 뒤 펼쳤을 때 마지막에 칠해지지 않은 넓이를 구한다.

어려움9기하시뮬레이션구현분할 정복아직 제출이 없습니다시간 제한2초메모리 제한128 MB

문제

지민이는 가로가 W, 세로가 H인 직사각형 종이를 가지고 있다. 지민이는 다음 과정을 K번 반복해 종이에 색을 칠한다. 0 <= i < K인 i번째 과정은 다음과 같다.

  1. 종이를 직선 x = f[i]를 따라 접는다. 왼쪽 부분이 오른쪽 부분 위로 올라가도록 접는다.
  2. 현재 종이를 가로 방향으로 c[i] + 1개의 높이가 같은 구간으로 나눈 뒤, 위쪽 구간부터 차례대로 c[i]번 접는다.
  3. 현재 접힌 상태에서 가장 왼쪽 아래 점을 (0, 0)으로 잡는다. 왼쪽 아래 꼭짓점이 (x1[i], y1[i])이고 오른쪽 위 꼭짓점이 (x2[i], y2[i])인 직사각형 영역을 칠한다. 물감은 겹쳐진 모든 종이층에 스며든다.
  4. 종이를 다시 펼친다.

모든 과정이 끝난 뒤, 색칠되지 않은 영역의 넓이를 구하시오.

입력

첫째 줄에 세 정수 W, H, K가 주어진다.

다음 K개의 줄에는 각각 한 번의 접기와 색칠 정보를 나타내는 여섯 정수 f[i], c[i], x1[i], y1[i], x2[i], y2[i]가 주어진다.

출력

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

제한

  • 1 <= W, H <= 10^9
  • 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)