USACO 2011 Nov Silver
Problem 2. Cow Lineup
Cow Lineup
Problem 2: Cow Lineup [Brian Dean]
Farmer John has hired a professional photographer to take a picture of some of his cows. Since FJ’s cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.
FJ’s N cows are all standing at various positions along a line, each described by an integer position (i.e., its x coordinate) as well as an integer breed ID. FJ plans to take a photograph of a contiguous range of cows along the line. The cost of this photograph is equal its size – that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.
Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ’s herd.
PROBLEM NAME: lineup
INPUT FORMAT:

Line 1: The number of cows, N (1 <= N <= 50,000).

Lines 2..1+N: Each line contains two spaceseparated positive integers specifying the x coordinate and breed ID of a single cow. Both numbers are at most 1 billion.
SAMPLE INPUT (file lineup.in):
6
25 7
26 1
15 1
22 3
20 1
30 1
INPUT DETAILS:
There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.
OUTPUT FORMAT:
 Line 1: The smallest cost of a photograph containing each distinct breed ID.
SAMPLE OUTPUT (file lineup.out):
4
OUTPUT DETAILS:
The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ’s herd.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
ll N, K;
int main() {
setIO("lineup");
cin >> N >> K;
vector<int> cows(N);
F0R(i, N) {
cin >> cows[i];
}
int amt = 0;
int ans = 0;
map<int, int> count;
int l = 0, r = 0;
while (r < N) {
while (amt > K + 1) {
count[cows[l]];
if (count[cows[l]] == 0) {
amt;
}
l++;
}
if (count[cows[r]] == 0) {
amt++;
}
count[cows[r]]++;
ans = max(count[cows[r]], ans);
r++;
}
cout << ans;
}