RiseOJ – 소는 왜 길을 건넜을까 III

설명

농부 존은 앞선 두 문제에서 소개된, 소들이 농장을 지나는 도로를 건너는 문제를 계속 고민하고 있다. 그는 이제 친함의 기준이 이전에 생각했던 것보다 조금 더 미묘하다는 것을 깨닫는다. 이제 품종 $$a$$ 와 $$b$$ 는 $|a - b| \leq K$ 이면 친하고, 그렇지 않으면 친하지 않다.

FJ의 농장을 지나는 도로 양쪽의 들판 순서가 주어질 때, 친하지 않은 교차 품종 쌍의 개수를 세시오. 교차 품종 쌍의 정의는 앞선 문제들과 같다.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ ( $1 \leq N \leq 100,000$ )과 $$K$$ ( $0 \leq K < N$ )가 주어진다. 다음 $$N$$ 개의 줄은 도로 한쪽 들판들의 순서를 품종 ID로 나타낸다. 각 품종 ID는 $1 \ldots N$ 범위의 정수이다. 마지막 $$N$$ 개의 줄은 도로 다른 쪽 들판들의 순서를 품종 ID로 나타낸다. 각 품종 ID는 각 순서에 정확히 한 번씩 나타난다.

출력 형식

친하지 않은 교차 품종 쌍의 개수를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 friendcross.in · 출력을 쓸 파일 friendcross.out

예제 1

입력

출력

설명

In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Platinum

올림피아드 > USACO > 2016-2017 > February > Platinum

태그

JudgeUSACO

소는 왜 길을 건넜을까 III

평가 및 의견

풀이 제출