문제
정오리카 공화국은 1번 도시부터 n번 도시까지 n개의 도시가 있다.
각 도시는 일직선 위에 놓여있다.
각각의 도시에는 하나의 통신 기지가 있다.
i번 도시에 있는 통신 기지의 수신기는 그 세기가 bi이고, 발신기는 그 세기가 ai이다.
("발신"이라 함은 신호를 보내는 것을 뜻하고, "수신"이라 함은 신호를 받는 것을 뜻한다.)
어떤 두 도시 i, j에 있어서, |i-j| ≤ ai+bj이면 i에서 j로 신호를 보낼 수 있다.
(|a|는 절대값 a를 뜻하며, 절대값 a는, a의 부호를 뗀 수치만을 뜻한다.)
어떤 도시 i, j, k에 있어서 i에서 j로 신호를 보낼 수 있고, j에서 k로도 보낼 수 있다면, i에서 k로도 신호를 보낼 수 있다.
직접, 또는 다른 도시를 통해서 i번 도시에서 j번 도시로 신호를 보내는 것이 가능하고,
j번 도시에서 i번 도시로도 신호를 보내는 것이 가능하다면 i번 도시와 j번 도시는 상호 통신 가능하다고 한다.
정오리카 공화국 대통령인 김정올은 상호 통신 가능한 도시 쌍 (i, j) (단 i < j)의 수를 모두 구하려고 한다.
그래서 당신의 도움이 필요하다. 이를 구하는 프로그램을 작성하라.
입력
첫 줄에 도시의 수인 정수 n이 주어진다.
둘째 줄에는 a1, a2, … an 이 공백을 사이에 두고 주어진다.
이는 각 도시의 발신기의 세기이다.
셋째 줄에는 b1, b2,…bn이 공백을 사이에 두고 주어진다.
이는 각 도시의 수신기의 세기이다.
제약 조건
모든 부분문제에서 1 ≤ n ≤ 200,000 을 만족한다.
모든 부분문제에서 ai 와 bi는 0이상 n 이하의 정수이다.
출력
상호 통신 가능한 도시 쌍 (i, j) (단, i < j)의 수를 모두 출력하라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 6점 | n≤100을 만족한다. |
| #2 | 19점 | n≤5,000을 만족하고, ai와 bi는 0 또는 1이다. |
| #3 | 13점 | n≤5,000을 만족한다. |
| #4 | 62점 | 주어진 제약 조건 외에 아무 제약조건이 없다. |
예제 #1
6
0 0 1 0 0 2
0 0 1 0 0 1
4
예제 #2
6
6 6 6 6 6 6
6 6 6 6 6 6
15
로그인해야 코드를 작성할 수 있어요.