[Silver III] 다이나믹 롤러 - 17393 (이분탐색)

[Silver III] 다이나믹 롤러 - 17393

문제 링크

성능 요약

메모리: 139588 KB, 시간: 3984 ms

분류

이분 탐색(binary_search)

문제 설명

페인팅 전문 회사 부키치 암즈는 거대한 페인팅용 롤러 "다이나믹 롤러"를 출시하였다. 이 신제품은 평범한 페인팅 롤러와 마찬가지로 굴려서 칠할 수 있지만, 손잡이를 세로로 휘둘러 잉크를 한번에 흩뿌릴 수도 있도록 설계되었다. 이러한 새로운 사용방법은 거대한 몸집과 맞물려 매우 역동적으로 보였기 때문에, 이 롤러의 이름은 다이나믹 롤러가 되었다. 평소 페인팅에 관심이 많던 멩미는 다이나믹 롤러의 매력에 흠뻑 빠져, 단숨에 다이나믹 롤러를 구매했다. 지금 당장 롤러를 시험해 보고 싶었던 멩미는 통로 일부분을 칠해보기로 했다.

통로는 1 × N 길이의 일자 형태를 가지고 있고, 통로의 바닥은 1 × 1 타일로 가득 차있다. 각 타일은 잉크지수 Ai 와 점도지수 Bi 를 가지고 있다. 타일이 제각각 다른 특성을 가지고 있기 때문에, 멩미는 세심하게 롤러를 휘둘러야만 한다. 멩미가 i 번째 타일 위에 서 있을 때, 멩미는 다이나믹 롤러로 현재 위치보다 오른쪽에 있으면서 점도지수가 서 있는 칸의 잉크지수 Ai 이하인 칸을 칠할 수 있다.

통로는 기본적인 관리가 되고 있기 때문에, 각 칸의 잉크지수 Ai 는 점도지수 Bi 이상이다. 그러나 깊숙한 통로는 관리에 어려움이 있기 때문에, 점도지수 Bi 는 항상 오름차순이다. 이런 상황 속에서 멩미가 통로의 각 타일에서 서 있을 때 다이나믹 롤러로 칠할 수 있는 최대의 칸 수를 구해보자.

입력

첫 번째 줄에 통로의 길이인 자연수 N이 입력으로 주어진다. (1 ≤ N ≤ 5 × 105)

두 번째 줄에 N개의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다. Ai 는 i 번째 칸의 잉크지수를 의미한다. (1 ≤ Aᵢ ≤ 1018)

세 번째 줄에 N개의 정수 B1, B2, ..., BN이 공백으로 구분되어 주어진다. Bi 는 i 번째 칸의 점도지수를 의미한다. (1 ≤ Bᵢ ≤ 1018, Ai ≥ Bi)

B1, B2, ..., BN은 오름차순이다. 즉, 1 ≤ i ≤ j ≤ N을 만족하는 모든 정수 순서쌍 (i, j)에 대해 Bi ≤ Bj 가 성립한다.

출력

첫 번째 줄에 N개의 정수 x1, x2, ..., xN을 공백으로 구분하여 출력한다. xi는 i 번째 칸에 서서 다이나믹 롤러를 사용할 때 최대로 칠할 수 있는 칸의 개수이다.

그냥 조건문으로 구현하면 시간초과가 난다. 이분탐색을 통해 ink를 기준으로 점도를 이분탐색으로 탐색해가며 인덱스를 구해서 갯수를 저장하여 출력해주면 문제 해결.