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 \le d_n \le X)~, starting $s$ ~s~ $(1 \le s < Y)$ ~(1 \le 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 \le s < X)~ to the right of the left edge of the sheet.