MWC '15 #4 P5: Arts and Crafts

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 0.6s

Memory limit: 256M

Author:

aurpine

Problem type

icicreampoph is doing some arts and crafts. Hypothetically speaking, he is cutting horizontal and vertical lines on an $X$ $X$ by $Y$ $Y$ sheet of paper. He has two tools, a pair of scissors and a paper cutter. The paper cutter will always cut the whole sheet (from one end to another). With the scissors though, he can choose how deep to cut the paper. Unfortunately, the paper cutter is set up to only cut vertically, and thus, he will only use the scissors to cut horizontally. Before he actually cuts the paper, he wants to know how many pieces of paper he will end up with after the $N$ $N$ cuts.

A piece of paper is freed when all 4 sides of the rectangular area are cut (including the original edges of the paper). He may cut multiple times at the same spot. When this happens, infinitely small pieces of paper will not be created, i.e., the longer cut takes precedence.

Input Specification

Three space separated integers, $N$ $N$ , $X$ $X$ and $Y$ $Y$ .

$N$ $N$ lines follow, of the form:

h s d a horizontal cut of depth $d_n$ $d_{n}$ $(1 \le d_n \le X)$ $(1 \leq d_{n} \leq X)$ , starting $s$ $s$ $(1 \le s < Y)$ $(1 \leq s < Y)$ above the bottom of the piece of paper.
v s a vertical cut from the top to the bottom, starting $s$ $s$ $(1 \le s < X)$ $(1 \leq s < X)$ to the right of the left edge of the sheet.

Constraints

Subtask 1 [5%]

$0 \le N \le 20$ $0 \leq N \leq 20$

$1 \le X,Y \le 100$ $1 \leq X, Y \leq 100$

Subtask 2 [5%]

$0 \le N \le 40\,000$ $0 \leq N \leq 40 000$

$1 \le X,Y \le 10^4$ $1 \leq X, Y \leq 10^{4}$

Subtask 3 [90%]

$0 \le N \le 100\,000$ $0 \leq N \leq 100 000$

$1 \le X,Y \le 10^9$ $1 \leq X, Y \leq 10^{9}$

Note: fast input may be required.

Output Specification

The number of pieces of paper that icicreampoph will end up with after performing the cuts.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

The cuts are shown in the picture below. The gold numbers show the pieces of paper.

$\text{[math]}$

Comments

-1

Jeffmagma commented on April 17, 2016, 7:03 p.m.

Is it possible that he will cut at a non-integer spot?

-1

atarw commented on April 17, 2016, 7:23 p.m. ← edit 3 →

No