IOI '14 - Taipei, Taiwan

Wall

Jian-Jia is building a wall by stacking bricks of the same size ogether. This wall consists of n columns of bricks, which are numbered 0 to n − 1 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 k phases of adding or removing bricks. The building process completes when all k phases are finished. In each phase Jian-Jia is given a range of consecutive brick columns and a height h, 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 h bricks, so that they have exactly h bricks. He does nothing on the columns having h or more bricks.
• In a removing phase, Jian-Jia removes bricks from those columns in the given range that have more than h bricks, so that they have exactly h bricks. He does nothing on the columns having h bricks or less.

Your task is to determine the final shape of the wall.

Example

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

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

Given the description of the k phases, please calculate the number of bricks in each column after all phases are finished.

Input Format

Line 1 of input consists of the two integers n, and k. n is the number of columns of the wall, and k is the number of phases.
Line 2 + i of input each consists of the format: op[i], left[i], right[i], and height[i].

• op[i] is the type of phase i: 1 for an adding phase and 2 for a removing phase, for 0 ≤ i ≤ k − 1.
• the range of columns in phase i starts with column left[i] and ends with column right[i] (including both endpoints left[i] and right[i]), for 0 ≤ i ≤ k − 1. You will always have left[i] ≤ right[i].
• height[i] is the height parameter of phase i, for 0 ≤ i ≤ k − 1.

Output Format

The output should consist of n integers, one per line, describing the result. Line i should describe the final number of bricks in column i, for 0 ≤ i ≤ n − 1.

Sample Input 1

10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412

Sample Output 1

0
0
0
39412
39412
39412
48623
48623
48623
48623

Sample Input 2

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

Sample Output 2

3
4
5
4
3
3
0
0
1
0

Subtasks

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

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 3.00s
Memory Limit: 256M
Added: Jul 29, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)