题目描述
三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶，一直到1000秒。第二个农民在700秒开始，在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。
你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位):
最长至少有一人在挤奶的时间段。
最长的无人挤奶的时间段。（从有人挤奶开始算起）
输入输出格式
输入格式：
Line 1:
一个整数N。
Lines 2..N+1:
每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。
输出格式：
一行，两个整数，即题目所要求的两个答案。
输入输出样例
输入样例#1：
3300 1000700 12001500 2100
输出样例#1：
900 300
说明
题目翻译来自NOCOW。
USACO Training Section 1.2
时间区间我用的左闭右开、
线段树区间修改，最后统计最大值、
1 #include2 3 #define max(a,b) (a>b?a:b) 4 5 const int N(1000005); 6 int n,cnt,l[N],r[N],have[N]; 7 struct Tree { 8 bool flag; 9 int l,r,val; 10 }tr[N<<2]; 11 12 #define lc (now<<1) 13 #define rc (now<<1|1) 14 #define mid (tr[now].l+tr[now].r>>1) 15 void Tree_build(int now,int l,int r) 16 { 17 tr[now].l=l; tr[now].r=r; 18 if(l==r) 19 { 20 tr[now].val=1; 21 tr[now].flag=0; 22 return ; 23 } 24 Tree_build(lc,l,mid); 25 Tree_build(rc,mid+1,r); 26 } 27 void Tree_down(int now) 28 { 29 if(tr[now].l==tr[now].r) return ; 30 tr[lc].flag=1; tr[lc].val=0; 31 tr[rc].flag=1; tr[rc].val=0; 32 } 33 void Tree_add(int now,int l,int r) 34 { 35 if(tr[now].l==l&&tr[now].r==r) 36 { 37 tr[now].val=0; 38 tr[now].flag=1; 39 return ; 40 } 41 if(tr[now].flag) Tree_down(now); 42 if(r<=mid) Tree_add(lc,l,r); 43 else if(l>mid) Tree_add(rc,l,r); 44 else Tree_add(lc,l,mid),Tree_add(rc,mid+1,r); 45 } 46 void Tree_push(int now) 47 { 48 if(tr[now].l==tr[now].r) 49 { 50 have[++cnt]=tr[now].val; 51 return ; 52 } 53 if(tr[now].flag) Tree_down(now); 54 Tree_push(lc); Tree_push(rc); 55 } 56 57 inline void read(int &x) 58 { 59 x=0; register char ch=getchar(); 60 for(;ch>'9'||ch<'0';) ch=getchar(); 61 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; 62 } 63 64 int AC() 65 { 66 int R=0; read(n); 67 for(int i=1; i<=n; ++i) 68 { 69 read(l[i]);read(r[i]); 70 R=max(R,r[i]); 71 } 72 Tree_build(1,1,R); 73 for(int i=1; i<=n; ++i) 74 Tree_add(1,l[i]+1,r[i]); 75 Tree_push(1); 76 int ans1=0,ans2=0,tmp; 77 for(int i=1; i<=cnt; ++i) 78 { 79 if(have[i]) continue; 80 tmp=1; 81 for(int j=i+1; j<=cnt; j++) 82 { 83 if(have[j]==have[j-1]) tmp++; 84 else 85 { 86 if(have[j-1]) ans2=max(ans2,tmp); 87 else ans1=max(ans1,tmp); 88 tmp=1; 89 } 90 } 91 if(have[cnt]) ans2=max(ans2,tmp); 92 else ans1=max(ans1,tmp); 93 break; 94 } 95 printf("%d %d\n",ans1,ans2); 96 return 0; 97 } 98 99 int Hope=AC();100 int main(){;}