문제
선 위에 m개의 색상을 가진 n개의 서로 다른 점이 있으며, m ≤ n입니다. S를 이 점들의 집합이라 합시다. 다음을 만족하는 공집합이 아닌 부분집합 C ⊆ S를 선택하려고 합니다.
S - C에 속하지 않는 모든 점 p에 대해, C에 있는 점들 중 p에 가장 가까운 점은 p와 같은 색을 갖습니다. 물론, C에 p에 가장 가까운 점이 두 개 이상 있다면, 그중 하나가 p와 같은 색을 갖는 것으로 충분합니다.
예를 들어, 그림 G.1에는 두 가지 색상으로 1부터 6까지 레이블이 지정된 여섯 개의 점이 있습니다. 점 4와 5는 빨간색이고 나머지는 파란색입니다. 집합 {2, 4, 6}은 위의 성질을 만족합니다. 그러나 집합 {2, 4}는 이 성질을 만족하지 않습니다. {2, 4}에서 점 6에 가장 가까운 점은 점 4이고, 이는 점 6의 색상과 다르기 때문입니다. 실제로 집합 {2, 4, 6}은 이 성질을 만족하는 최소 기수 부분 집합입니다.
선 위에 서로 다른 n개의 점과 m개의 점이 주어졌을 때, 위 속성을 만족하는 최소 기수를 갖는 S의 비어 있지 않은 부분 집합 C를 찾고 최소 기수를 출력하는 프로그램을 작성하세요.
입력
입력은 두 개의 정수 m과 n(1 ≤ m ≤ n ≤ 100,000)을 포함하는 줄로 시작합니다. 여기서 m은 색상의 수이고 n은 점의 수입니다. 점은 줄의 왼쪽에서 오른쪽으로 1부터 n까지 번호가 매겨지고 색상은 1부터 m까지 번호가 매겨집니다. 두 번째 줄에는 n개의 정수가 증가하는 방식으로 정렬된 시퀀스가 들어 있으며, i번째 숫자는 점 i의 좌표입니다. 점의 좌표 x는 0 ≤ x ≤ 10 9을 만족하고 모두 서로 다릅니다. 세 번째 줄에는 n개의 정수 시퀀스가 들어 있으며, i번째 숫자는 1과 m 사이의 점 i의 색상입니다.
출력
정확히 한 줄을 출력하세요. 위 성질을 만족하기 위해 S의 공집합이 아닌 부분집합 C의 최소 기수가 이 줄에 포함되어야 합니다.
예제 #1
2 6
0 3 4 7 8 11
1 1 1 2 2 1
3
예제 #2
2 6
0 3 4 7 8 11
1 2 1 2 2 1
5
로그인해야 코드를 작성할 수 있어요.