This page is still under construction.

Parts of this page are still being built. What you see may change.

Folded Paper Painting

Time limit2sMemory limit128 MB

Summary
Simulate K rounds of folding a W by H rectangle along a vertical line and several horizontal folds, painting one rectangle each round through all layers, and report the unpainted area at the end.
Level

Hard9 of 10

Topics
Geometry, Simulation, Implementation, Divide and conquer
Solved
No attempts yet

Problem

Jimin has a rectangular sheet of paper with width W and height H. Jimin will repeat the following painting process K times. For the i-th process, where 0 <= i < K, do the following:

  1. Fold the paper along the line x = f[i]. The part on the left is folded onto the part on the right.
  2. Divide the current paper horizontally into c[i] + 1 intervals of equal height, then fold it c[i] times, starting from the uppermost interval and proceeding downward.
  3. In the current folded state, take the lower-left point of the folded paper as (0, 0). Paint the rectangle whose lower-left corner is (x1[i], y1[i]) and whose upper-right corner is (x2[i], y2[i]). The paint soaks through every overlapping layer of paper.
  4. Unfold the paper.

After all processes are complete, find the area that is still unpainted.

Input

The first line contains three integers W, H, and K.

Each of the next K lines contains six integers f[i], c[i], x1[i], y1[i], x2[i], and y2[i], describing one folding and painting process.

Output

Print the area of the unpainted region.

Constraints

  • 1 <= W, H <= 10^9
  • 1 <= K <= 50
  • 0 <= f[i] <= W
  • 0 <= c[i] <= 1,000
  • c[i] + 1 is a divisor of H
  • 0 <= x1[i] < x2[i] <= max(f[i], W - f[i])
  • 0 <= y1[i] < y2[i] <= H / (c[i] + 1)

Examples7

  1. Example 1

    Input
    6 6 2
2 1 1 2 3 3
5 2 2 0 4 2
    Expected output
    18

  2. Example 2

    Input
    5 6 1
2 2 1 1 3 2
    Expected output
    21

  3. Example 3

    Input
    2 4 2
0 1 0 1 2 2
0 0 0 1 1 4
    Expected output
    3

  4. Example 4

    Input
    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
    Expected output
    27

  5. Example 5

    Input
    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
    Expected output
    336

  6. Example 6

    Input
    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
    Expected output
    1319

  7. Example 7

    Input
    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
    Expected output
    20