페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10337

공정한 결투 30s 1024MB

문제

앙 가르드(En garde)! 검술 대회 결승전에서 찰스(Charles)와 델릴라(Delila)가 맞붙으려 한다.

펜싱 경기장 한쪽 벽에는 서로 다른 N가지 종류의 검이 걸려 있는 거치대가 있다. 검의 종류는 1부터 N까지 번호가 매겨져 있다. 수석 심판인 당신은 (L, R)이라는 정수 쌍(1 ≤ L ≤ R ≤ N)을 선택하고, 이 결투에서는 L번째부터 R번째까지(포함) 종류의 검만 사용할 수 있게 된다.

검의 종류마다 사용법이 다르며, 한 종류의 검을 잘 다룬다고 해서 다른 종류도 잘 다룬다는 보장은 없다! 찰스와 델릴라는 i번째 종류의 검에 대해 각각 Ci, Di의 숙련도를 가진다. 두 사람은 당신이 사용할 수 있게 만든 검의 종류들을 보고, 각자 그중에서 자신이 가장 숙련된 종류를 선택한다. 어떤 전사가 여러 종류에 대해 동일한 최고 숙련도를 가지고 있고, 그 숙련도가 다른 모든 사용 가능한 종류에서의 숙련도보다 더 크다면, 그 전사는 그 최고 숙련도에 해당하는 종류들 중 하나를 무작위로 고른다. 찰스와 델릴라가 같은 종류의 검을 선택할 수도 있는데, 그것은 문제없다 — 각 종류의 검은 여러 자루씩 준비되어 있다.

찰스가 선택한 검의 숙련도와 델릴라가 선택한 검의 숙련도의 차이의 절댓값이 K 이하이면 결투는 공정하다고 한다. 결투를 흥미롭게 만들기 위해, 당신은 공정한 결투가 되도록 만드는 (L, R) 선택이 총 몇 가지인지 알고 싶다.


입력

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 위에서 설명한 정수 N과 K가 주어진 한 줄로 시작한다. 그 다음 두 줄이 더 이어진다. 첫째 줄에는 N개의 정수 Ci가 주어지며, i번째 값은 i번째 종류의 검에 대한 찰스의 숙련도이다. 마찬가지로 둘째 줄에는 N개의 정수 Di가 주어지며, i번째 값은 델릴라의 숙련도이다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 위에서 설명한 대로 공정한 결투가 되도록 만드는 (L, R) 선택의 개수이다.


예제 

6
4 0
1 1 1 8
8 8 8 8
3 0
0 1 1
1 1 0
1 0
3
3
5 0
0 8 0 8 0
4 0 4 0 4
3 0
1 0 0
0 1 2
5 2
1 2 3 4 5
5 5 5 5 10
Case #1: 4
Case #2: 4
Case #3: 1
Case #4: 0
Case #5: 1
Case #6: 7
샘플 케이스 #1에서는 Charles가 마지막 종류의 검을 사용할 수 있을 때 그리고 그때에만 결투가 공정하므로 답은 4다. 샘플 케이스 #2에서 공정한 결투는 4개: (1, 2), (1, 3), (2, 2), (2, 3)이다. (1, 3) 같은 경우 Charles와 Delila가 각각 가장 숙련된 검을 여러 개 가질 수 있지만, 각 쌍은 공정한 결투 1개로만 센다는 점에 유의하라. 샘플 케이스 #3에서는 공정한 결투가 1개: (1, 1)이다. 샘플 케이스 #4에서는 공정한 결투가 없으므로 답은 0이다. 샘플 케이스 #5에서 결투자들은 공정하게 만들려고 하는 것이 아니라 자신이 가장 숙련된 검을 고른다는 점을 기억하라. 예를 들어 (1, 3)은 공정한 결투가 아니다. Charles는 1번 검을, Delila는 3번 검을 선택할 것이기 때문이다. Delila는 더 약한 검을 골라 Charles를 봐주지 않는다! 샘플 케이스 #6에서는 공정한 결투가 7개: (1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)이다.

출처

GCJ 2019r1b C

로그인해야 코드를 작성할 수 있어요.