Three Primary Colors
Time limit3sMemory limit256 MB
Given up to 25,000 colored rectangles painted one at a time without repainting already covered pixels, report the total area of each of the seven resulting color regions.
- Level
Hard8 of 10
- Topics
- Divide and conquer, Segment tree, Prefix sum, Sorting
- Solved
- No attempts yet
Problem
There are rectangles on a plane with an x-axis and a y-axis. Minsung will now use an enormous printer to color the rectangles on this plane.
Minsung has ink in three colors: cyan, yellow, and magenta. He can paint some rectangles cyan, some yellow, and others magenta.
When two or more rectangles overlap, a region can appear whose color is not one of the three inks Minsung has. The figure below shows the colors that can appear when cyan, yellow, and magenta are mixed.
\
Figure 1: CMYK, the three primary colors of subtractive mixing.
That is, red is magenta and yellow mixed in equal parts, green is yellow and cyan, blue is magenta and cyan, and black is magenta, yellow, and cyan mixed in equal parts.
To save ink, Minsung decided that once he has painted a place with a color, he will not paint it again even if an overlapping rectangle of the same color appears later. For example, if he paints the region from (0, 0) to (2, 2) yellow and then needs to paint from (1, 1) to (3, 3) yellow again, the region from (1, 1) to (2, 2) is already yellow, so he does not paint yellow over it again. This keeps the mixing ratio of the three primary colors always the same, so Minsung saves ink and no color outside the figure above can appear.
Given the rectangles to be painted in different colors, you want to find the area of each color after Minsung has painted everything in the given colors, before he paints each region one by one.
Input
The first line gives the number of rectangles to read, N. (1 ≤ N ≤ 25,000)
The next N lines each give the integers x1, y1, x2, y2 and the character c describing a rectangle, separated by spaces. (-108 ≤ x1 < x2 ≤ 108, -108 ≤ y1 < y2 ≤ 108)
This means the rectangle has vertices (x1, y1), (x1, y2), (x2, y2), (x2, y1) and its region is painted with the color corresponding to c.
Every c is a one-character string, one of “C” (cyan), “M” (magenta), or “Y” (yellow).
Output
On the first line, print seven integers Sc, Sm, Sy, Sr, Sg, Sb, Sk separated by spaces. They are the area of the cyan region, the area of the magenta region, the area of the yellow region, the area of the red region, the area of the green region, the area of the blue region, and the area of the black region, respectively. (CMY RGB K)
The rectangle with vertices (0,0), (1,0), (1,1), (0,1) has area 1.