수열과 개구리

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

요약

각 시작 위치에서 개구리가 b_x초를 기다린 뒤 x±a_x로 이동할 때, 수열 밖으로 나가는 최초 시각 f(x)를 모두 구한다.

문제

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

이 수열 위에 개구리 한 마리가 있습니다. 개구리는 초기에 어떤 정수 위치 $1 \le x \le n$ 에서 출발하며, 자신의 위치가 수열 밖 $^\dagger$ 이 될 때까지 다음을 반복합니다.

$b\_x$ 초 동안 기다린 뒤, 위치 $x-a\_x$ 로 이동하거나 위치 $x+a\_x$ 로 이동합니다. 이때 이동한 위치가 $x$ 의 새로운 값이 됩니다.

개구리가 시작하는 위치 $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비트 정수의 최댓값을 초과할 수 있음에 유의하세요. 값을 저장하기 위해 다음을 사용할 것을 권장합니다.