IOI '14 P2 - Wall (Standard I/O)

View as PDF

Submit solution

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

Problem type

Jian-Jia is building a wall by stacking bricks of the same size together. 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.

phase type range height
0 add columns 1 to 8 4
1 remove columns 4 to 9 1
2 remove columns 3 to 6 5
3 add columns 0 to 5 3
4 add columns 2 5
5 remove columns 6 to 7 0

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 Specification

  • 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],\text{ and }height[i].
    • op[i] is the type of phase i: 1 for an adding phase and 2 for a removing phase, for 0 \le i \le 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 \le i \le k - 1. You will always have left[i] \le right[i].
    • height[i] is the height parameter of phase i, for 0 \le i \le k - 1.

Output Specification

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 \le i \le 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 or equal to 100\,000.

subtask points n k note
1 8 1 \le n \le 10\,000 1 \le k \le 5\,000 no additional limits
2 24 1 \le n \le 100\,000 1 \le k \le 500\,000 all adding phases are before all removing phases
3 29 1 \le n \le 100\,000 1 \le k \le 500\,000 no additional limits
4 39 1 \le n \le 2\,000\,000 1 \le k \le 500\,000 no additional limits

Comments

There are no comments at the moment.