Bulgarian OI '09 P4 - Frogs

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 1.0s
Memory limit: 16M
Problem types
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 (1 \le N \le 10^6).
On the second line the N natural numbers H_i (1 \le H \le 10^9) are given, separated by spaces. The third line contains the N natural numbers J_i (1 \le J \le 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


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

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

static int readInt() throws IOException{
    int x = 0, c;
    while((c = br.read()) != ' ' && c != '\n')
        x = x * 10 + (c - '0');
    return x;
}