레이팅 미적용설명
FJ의 소 N마리(1 <= N <= 100,000)가 길고 곧은 1차원 울타리를 따라 여러 위치에 서 있다. i번째 소는 위치 x_i(0...1,000,000,000 범위의 정수)에 서 있고 품종은 b_i(1..8 범위의 정수)이다. 같은 위치에 두 마리가 서 있는 경우는 없다.
FJ는 연속한 구간의 소들을 사진에 담고 싶은데, 사진에 어떤 품종들이 등장하든 각 품종의 수가 같아야 한다. 또한 농부 존은 (전체 8개 품종 중) 최소 K개(K >= 2)의 품종이 사진에 나오길 원한다. 이 조건을 만족하는 사진의 최대 크기를 찾아 FJ를 도와라. 사진의 크기는 사진에 담긴 소들의 최대 위치와 최소 위치의 차이다.
FJ의 조건을 만족하는 사진이 없으면 대신 -1을 출력한다.
제약
입력 형식
첫째 줄: 공백으로 구분된 N과 K가 주어진다.
둘째 줄부터 N+1째 줄까지: 각 줄에 소 하나를 나타내는 두 정수 x(i)와 품종 번호가 주어진다.
출력 형식
공정한 사진의 최대 크기를 정수 하나로 출력한다. 그러한 사진이 없으면 -1을 출력한다.
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:
입력을 읽을 파일
fairphoto.in · 출력을 쓸 파일 fairphoto.out예제 1
입력
9 2
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3출력
6설명
Output details: The range from x=2 to x=8 has 2 each of breeds 1, 2, and 3.
문제 정보
태그