## IOI '14 P2 - Wall

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
C, C++

Jian-Jia is building a wall by stacking bricks of the same size together. This wall consists of columns of bricks, which are numbered to from left to right. The columns may have different heights. The height of a column is the number of bricks in it.

Jian-Jia builds the wall as follows. Initially there are no bricks in any column. Then, Jian-Jia goes through phases of adding or removing bricks. The building process completes when all phases are finished. In each phase Jian-Jia is given a range of consecutive brick columns and a height , and he does the following procedure:

• In an adding phase, Jian-Jia adds bricks to those columns in the given range that have less than bricks, so that they have exactly bricks. He does nothing on the columns having or more bricks.
• In a removing phase, Jian-Jia removes bricks from those columns in the given range that have more than bricks, so that they have exactly bricks. He does nothing on the columns having bricks or less.

#### Example

We assume that there are brick columns and wall building phases. All ranges in the following table are inclusive. Diagrams of the wall after each phase are shown below.

phase type range height
1 remove columns to
2 remove columns to
5 remove columns to

Since all columns are initially empty, after phase each of the columns to will have bricks. Columns and remain empty. In phase , the bricks are removed from columns to until each of them has brick, and column remains empty. Columns to , which are out of the given range, remain unchanged. Phase makes no change since columns to do not have more than bricks. After phase the numbers of bricks in columns , , and increase to . There are bricks in column after phase . Phase removes all bricks from columns and .

Given the description of the phases, please calculate the number of bricks in each column after all phases are finished. You need to implement the function buildWall.

• buildWall(n, k, op, left, right, height, finalHeight)
• n: the number of columns on the wall.
• k: the number of phases.
• op: array of length ; op[i] is the type of phase : for an adding phase and for a removing phase, for .
• left and right: arrays of length ; the range of columns in phase starts with column left[i] and ends with column right[i] (including endpoints left[i] and right[i]), for . You will always have left[i] right[i].
• height: array of length k; height[i] is the height parameter of phase , for .
• finalHeight: array of length ; you should return your results by placing the final number of bricks in column into finalHeight[i], for .

For all subtasks the height parameters of all phases are nonnegative integers less or equal to .

2 24 all adding phases are before all removing phases

#### Implementation details

Your submission should implement the subprogram described above using the following signatures.

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]);