수열과 개구리

면접 대비

시간 제한2초메모리 제한1024 MB

요약

배열 a와 b가 주어질 때, 개구리가 x에서 출발해 매번 b_x초를 기다린 뒤 a_x만큼 좌우로 뜁니다. 각 시작 위치에서 배열 밖으로 나가는 가장 빠른 시간을 구합니다.

문제

길이가 $n$ 이고 양의 정수로 이루어진 수열 $a$ 와 $b$ 가 있습니다. 두 수열의 인덱스는 $1$ 부터 시작합니다.

이 수열 위에 개구리 한 마리가 있습니다. 개구리는 처음에 정수 위치 $1 \le x \le n$ 중 한 곳에서 출발합니다. 자신의 위치가 수열 밖이 될 때까지 다음 과정을 반복합니다.

시작 위치 $x$ 에서 출발할 때, 개구리의 위치가 수열 밖이 될 수 있는 최초의 시각을 $f(x)$ 초라고 정의합니다. $f(1),f(2),\cdots,f(n)$ 의 값을 모두 구해야 합니다.

$^\dagger$ 어떤 위치 $x$ 에 대해서, $1 \le x \le n$ 이면 수열 안, $x<1$ 또는 $x>n$ 이면 수열 밖이라고 부릅니다.

첫 번째 줄에 두 수열의 길이 $n$ 이 주어집니다. ( $1 \le n \le 2 \cdot 10^5$ )

두 번째 줄에 $n$ 개의 정수 $a_1,a_2,\dots,a_n$ 이 공백으로 구분되어 주어집니다. ( $1 \le a_i \le n$ )

세 번째 줄에 $n$ 개의 정수 $b_1,b_2,\dots,b_n$ 이 공백으로 구분되어 주어집니다. ( $1 \le b_i \le 10^6$ )

$f(1),f(2),\cdots,f(n)$ 의 값을 순서대로 공백으로 구분하여 한 줄에 출력합니다.

이 문제의 제한에 따라 모든 $1 \le i \le n$ 에 대해 $f(i)$ 가 유한함을 증명할 수 있습니다.

출력이 32비트 정수의 최댓값을 넘을 수 있습니다. 값을 저장할 때는 다음 자료형을 사용하세요.