파일 업로드

비우호적인 품종

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

수찬은 품종이 우호적일 경우 일부 품종 간의 상호 작용이 실제로 허용된다는 것을 깨닫게 되는데, 이는 품종 ID 측면에서 쉽게 특성화할 수 있는 속성입니다. 품종 A와 B는 |a-b| ≤ K이면 우호적, 그렇지 않으면 비우호적입니다. 서로 우호적이라면 다른 품종이 지정된 밭으로 돌아다니는 것은 괜찮습니다.

수찬의 농장을 통과하는 도로의 양쪽에 N개의 밭이 순서대로 주어졌을 때(양쪽에 각 품종에 대해 정확히 하나의 밭이 있음), 두 밭이 교차하지 않고 각 횡단보도가 우호적인 두 품종이 포함된 한 쌍의 밭과 연결되도록 수찬이 자신의 도로 위에 그릴 수 있는 최대 횡단보도 수를 결정하도록 도와주세요. 각 필드는 최대 하나의 횡단보도를 통해서만 접근할 수 있습니다(따라서 횡단보도가 끝점에서 만나지 않도록 하세요).

길을 가로 지르는 수찬의 농장의 양쪽에 위치한 필드의 순서를 주어진대로 계산하여 비우호적인 품종 쌍의 수를 세어주세요.

💻 입력

입력의 첫 번째 줄에는 N (1 ≤ N ≤ 100,000)과 K (0 ≤ K < N)가 주어집니다. 다음 N개의 줄에는 도로 한쪽에 있는 밭의 종별 ID 순서를 설명합니다. 각 종별 ID는 1부터 N까지의 정수 범위 안에 있습니다. 마지막 N개의 줄에는 다른 한쪽 도로에 있는 밭의 종별 ID 순서를 설명합니다. 각 종별 ID는 각각 한 번씩만 나타납니다.

🖨️ 출력

비우호적인 교차 종의 쌍 수를 출력해 주세요.


💻 예제 입력 1
4 1
4
3
2
1
1
4
2
3
🖨️ 예제 출력 1
2

💡 힌트

이 예시에서는 종 1과 4는 비우호적이고 교차하며, 종 1과 3도 마찬가지로 비우호적이고 교차합니다.


출처: USACO 2017 February Contest, Platinum Problem 3. Why Did the Cow Cross the Road III