IOI '14 P2 - Wall

View as PDF

Submit solution


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 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. 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 k; 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.
    • left and right: arrays of length k; the range of columns in phase i starts with column left[i] and ends with column right[i] (including endpoints left[i] and right[i]), for 0 \le i \le k-1. You will always have left[i] \le right[i].
    • height: array of length k; height[i] is the height parameter of phase i, for 0 \le i \le k-1.
    • finalHeight: array of length n; you should return your results by placing the final number of bricks in column i into finalHeight[i], for 0 \le i \le n-1.

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

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[]);

Comments


  • 45
    Paradox  commented on May 31, 2017, 12:37 a.m.

    2000000 columns...
    that's a pretty long wall
    who's gonna pay for it?


    • 56
      wleung_bvg  commented on May 31, 2017, 1:09 a.m.

      MEXICOOOOO!