Bulgarian OI '09 P4 - Frogs

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
2009 Bulgarian Olympiad in Informatics

The frog-mutants in the metropolitan region have lost their mind. After years in the garbage, they are looking for a better life.

The boulevard they are living on is now fully covered with garbage bales. In particular, there are N bales, labeled from left to right with the numbers from 0 to N-1, with positive heights H_{i} (0 \le i <
N).

On each of the bales there is a frog that is very tired and can only make up to J_{i} (0 \le i < N) jumps. Every jump is to the nearest bale on the right that is strictly higher than the current bale. A frog that can jump over all the bales succeeds in leaving the city - indicated with a height of -1. Find the maximal height that each frog can reach.

Input Specification

On the first line is the number of bales N (0 \le N < 10^{6}).
On the second line the N natural numbers H_{i} (0 < H \le 10^{9}) are given, separated by spaces. The third line contains the N natural numbers J_{i} (0 < J < N), also separated by spaces.

Output Specification

Output N integers - the maximal height each frog can reach.

Sample Input 1

8
3 1 4 5 6 2 3 8
1 2 1 3 4 2 1 2

Sample Output 1

4 5 5 -1 -1 8 8 -1

Sample Input 2

6
7 8 9 1 2 3
2 2 2 2 2 2

Sample Output 2

9 -1 -1 3 -1 -1

Comments

There are no comments at the moment.