Solved by 139 users: ...
` <  <  <  <  <  <  <  <  <  < `

## Counting figures

Time limit = 8 second(s)

We have paper divided into M x N square cells, black and white. Black cells form joined figure (two cells are adjacent if their intersection is segment).

The description of the black figure is given as union of 1 x L (y-strip) and L x 1 (x-strip) tiles.

Strips can intersect and overlap, but two strips can not start at one cell. Starting cell of a strip is the cell with minimum rating. Cell rating is defined as x*N+y. Coordinates x and y are integers from sets 1..M and 1..N.

Question 1. What is the number of white cells?

Question 2. What is the number of joined white figures?

Each strip can be described by four numbers:

1) direction, D, that is 0 or 1: 0 — x-strip, 1 — y-strip;

2-3) coordinates of the starting cell, (X, Y);

4) strip length, L.

Strips are given in the order of starting cells.

Number of strips is less than 256000.

Input

The first line contains number P equal to 1 or 2. The second line contains M and N, 1 ≤ M ≤ 4000, 1 ≤ N ≤ 4000. Then number K follows, 0 ≤ K ≤ 256000, equal to number of strips. Then K lines, each with 4 numbers D X Y L, follow.

Output If P == 1 then output answer to the question 1.

If P == 2 then answer to the question 2.

 Input#1```1 40 400 2 1 1 100 40 0 1 101 1 ``` Output#1```15959 ```
 Input#2```2 40 400 2 1 1 100 40 1 1 101 1 ``` Output#2```2 ```
 Input#3```1 6 12 17 0 1 1 10 1 1 4 4 0 1 5 2 0 1 7 6 1 2 1 5 1 2 5 4 0 2 6 1 1 2 12 5 0 3 4 4 0 3 10 3 0 4 2 2 1 4 11 3 1 5 2 1 0 5 6 2 1 5 9 2 0 6 1 2 0 6 5 7 ``` Output#3```22 ```
 Input#4```2 6 12 12 0 1 1 12 1 1 12 6 1 2 1 5 0 2 4 3 0 3 4 4 0 3 10 3 1 3 11 4 0 4 1 5 1 5 2 2 0 5 5 3 1 5 9 2 0 6 5 8 ``` Output#4```3 ```

Author:
Moscow school contest, 2004
15 March 2004

<PREV | Problem set | Search related messages | NEXT>

 © acm.mipt DevGroupThe page was generated in 200ms