MWC '15 #4 P5: Arts and Crafts

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type

icicreampoph is doing some arts and crafts. Hypothetically speaking, he is cutting horizontal and vertical lines on a X by 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 cuts.

A piece of paper is freed when all 4 sides of the rectangular area is 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, X and Y.

N lines follow, of the form:

  • h s d a horizontal cut of depth d_n (1 \le d_n \le X) starting s (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 (1 \le s < X) to the right of the left edge of the sheet.


Subtask 1 [5%]

0 \le N \le 20

1 \le X,Y \le 100

Subtask 2 [5%]

0 \le N \le 40\,000

1 \le X,Y \le 10^4

Subtask 3 [90%]

0 \le N \le 100\,000

1 \le X,Y \le 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

3 4 6
h 3 4
h 1 3
v 2

Sample Output


Explanation for Sample Output

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


  • 0
    atarw  commented on April 17, 2016, 3:23 p.m. edit 2

    No (replying to jeffmagma)

  • 0
    Jeffmagma  commented on April 17, 2016, 3:03 p.m.

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