Solved by 139 users: ...
UserDateAttemptTimeCMSC
DAV`02 oct 2009`C++300.15284
Madiyar_Tktl`06 dec 2007`C++1700.48296
Madiyar_Tktl`06 dec 2007`C++1500.19316
checkil`28 may 2011`C++102.82316
Aion256`27 may 2011`C++302.88316
Aion256`26 may 2011`C++102.83318
DAV`31 jul 2008`C++200.15322
Ravent`23 aug 2006`FPC300.27324
asp`15 oct 2007`C++602.88328
Slam`08 jan 2005`C++4?.??335
kornakovBSU`03 oct 2009`C++800.11337
Ravent`23 aug 2006`FPC200.27338
Beybut1`27 feb 2007`FPC100.19343
Zaurbek_I`27 feb 2007`FPC700.19343
 C++ 73 FPC 44 Kylix 15 C 4 Java 3
` >  >  >  >  >  >  >  >  >  > `

## 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 210ms