bzoj#P3535. [Usaco2014 Open]Fair Photography
[Usaco2014 Open]Fair Photography
Statement
FJ's cows are standing at various positions along a long one-dimensional fence. The ith cow is standing at position and has breed . No two cows occupy the same position.
FJ wants to take a photo of a contiguous interval of cows for the county fair, but we wants all of his breeds to be fairly represented in the photo. Therefore, he wants to ensure that, for whatever breeds are present in the photo, there is an equal number of each breed (for example, a photo with each of breeds and is ok, a photo with of breeds , , and is ok, but of breed and of breed is not ok). Farmer John also wants at least breeds (out of the total) to be represented in the photo. Help FJ take his fair photo by finding the maximum size of a photo that satisfies FJ's constraints. The size of a photo is the difference between the maximum and minimum positions of the cows in the photo.
If there are no photos satisfying FJ's constraints, output instead.
Input Format
Line : and separated by a space.
Lines : Each line contains a description of a cow as two integers separated by a space: and its breed id.
Output Format
Line : A single integer indicating the maximum size of a fair photo. If no such photo exists, output .
9 2
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3
6
INPUT DETAILS:
$$\begin{aligned} \text{Breed ids:}&~1~2~3~\texttt{-}~1~1~2~3~1~~~\texttt{-}~\dots~~\texttt{-}~~~~~~1\\ \text{Locations:}&~1~2~3~4~5~6~7~8~9~10~\dots~99~100 \end{aligned} $$OUTPUT DETAILS:
The range from to has each of breeds , , and . The range from to has of breed , but this is invalid because and so we must have at least distinct breeds.
Constraints
$1 \le n \le 10^5,~0 \le x_i \le 10^9,~1 \le b_i \le 8,~k \le 2$