2009 Bulgarian Olympiad in Informatics
Task 4: Frog-Mutants
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 Hi (0 ≤ i < N).
On each of the bales there is a frog that is very tired and can only make up to Ji (0 ≤ 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
On the first line is the number of bales N (0 ≤ N < 106).On the second line the N natural numbers Hi (0 < H ≤ 109) are given, separated by spaces. The third line contains the N natural numbers Ji (0 < J < N), also separated by spaces.
Output
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
All Submissions
Best Solutions
Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 10, 2009
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)