USACO Milking Cows

Code

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
35
36
37
38
39
40
41
/*
ID: wcr19961
PROG: milk2
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
typedef long long LL;
const int maxn = 1000010;
int a[maxn];
int main() {
freopen("milk2.in", "r", stdin);
freopen("milk2.out", "w", stdout);
int n, l, r, L = maxn, R = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d", &l, &r);
L = min(L, l), R = max(R, r);
++a[l], --a[r];
}
int ans1 = 0, ans2 = 0, pre1 = maxn, pre2 = maxn, tmp = 0;
for (int i = L; i <= R; ++i) {
if (tmp > 0 && tmp + a[i] <= 0) {
pre2 = i;
ans1 = max(ans1, i - pre1);
}
if (tmp <= 0 && tmp + a[i] > 0) {
pre1 = i;
ans2 = max(ans2, i - pre2);
}
tmp += a[i];
}
printf("%d %d\n", ans1, ans2);
return 0;
}

支付宝扫码领红包