Line Reconstruction
Time limit1sMemory limit128 MB
Given N heights and, for each position, the count of earlier people with height at most that person's, reconstruct the original front-to-back order.
- Level
Medium6 of 10
- Topics
- Greedy, Sorting, Segment tree
- Solved
- No attempts yet
Problem
N people are standing in one line to enter a concert hall. For each person, consider how many people before them have height less than or equal to that person's height. Writing these values from the front of the line to the back gives a sequence S.
Given the N heights, where equal heights may appear multiple times, and the sequence S, reconstruct the exact order of heights in the original line.
Input
The first line contains the number of people N (1 <= N <= 100,000). Each of the next N lines contains one positive integer, the height of one person. Every height is at most 2 x 10^9. The last line contains the N integers of the sequence S, separated by spaces.
Output
Print N lines. On each line, print one height, in the order the people originally stood from front to back.