Bulgarian OI '09 P4 - Frogs

View as PDF

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

Problem type

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 bales, labeled from left to right with the numbers from to , with positive heights .

On each of the bales there is a frog that is very tired and can only make up to 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 . Find the maximal height that each frog can reach.

Input Specification

On the first line is the number of bales .
On the second line the natural numbers are given, separated by spaces. The third line contains the natural numbers , also separated by spaces.

Output Specification

Output 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

• commented on March 10, 2021, 5:24 p.m. edit 4

https://dmoj.ca/problem/btoi07p3#comment-13823

This applies here as well.

If you're getting MLE on Java, it may be because you're using BufferedReader and calling br.readLine(). 16M is not big enough to hold the second and third lines of input, which can be very long.

java.util.Scanner is too slow. I used br.read() to take input:

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

}