【HDU】1199 Color the Ball

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define MAXN 2010
  5 using namespace std;
  6 struct Line
  7 {
  8     int left,right,color;
  9 };
 10 Line p[MAXN];
 11 int x[MAXN<<2],tree[MAXN<<4];
 12 bool vis[MAXN<<2];
 13 inline void PushDown(int rt)
 14 {
 15     if(tree[rt]!=-1)
 16     {
 17         tree[rt<<1]=tree[rt<<1|1]=tree[rt];
 18         tree[rt]=-1;
 19     }
 20 }
 21 void Build(int L,int R,int rt)
 22 {
 23     if(L==R)
 24         tree[rt]=0;
 25     else
 26     {
 27         int mid=(L+R)>>1;
 28         tree[rt]=-1;
 29         Build(L,mid,rt<<1);
 30         Build(mid+1,R,rt<<1|1);
 31     }
 32 }
 33 void Update(int st,int en,int val,int L,int R,int rt)
 34 {
 35     if(st<=L&&R<=en)
 36         tree[rt]=val;
 37     else
 38     {
 39         int mid=(L+R)>>1;
 40         PushDown(rt);
 41         if(mid>=st)
 42             Update(st,en,val,L,mid,rt<<1);
 43         if(en>mid)
 44             Update(st,en,val,mid+1,R,rt<<1|1);
 45     }
 46 }
 47 void Query(int L,int R,int rt)
 48 {
 49     if(tree[rt]==1)
 50     {
 51         for(int i=L;i<=R;i++)
 52             vis[i]=true;
 53     }
 54     else if(tree[rt]==-1)
 55     {
 56         int mid=(L+R)>>1;
 57         Query(L,mid,rt<<1);
 58         Query(mid+1,R,rt<<1|1);
 59     }
 60 }
 61 int main()
 62 {
 63     char ch;
 64     int n,m,k,i,j,st,en;
 65     while(~scanf("%d",&n))
 66     {
 67         if(n==0)
 68         {
 69             puts("Oh, my god");
 70             continue;
 71         }
 72         for(k=i=0;i<n;i++)
 73         {
 74             scanf("%d%d %c",&p[i].left,&p[i].right,&ch);
 75             if(p[i].left>p[i].right)
 76                 swap(p[i].left,p[i].right);
 77             if(ch=='b')
 78                 p[i].color=0;
 79             else
 80                 p[i].color=1;
 81             x[k++]=p[i].left;
 82             x[k++]=p[i].right;
 83         }
 84         sort(x,x+k);
 85         k=unique(x,x+k)-x;
 86         for(i=k-1;i>0;i--)
 87         {
 88             if(x[i]!=x[i-1]+1)
 89                 x[k++]=x[i-1]+1;
 90         }
 91         sort(x,x+k);
 92         Build(0,k-1,1);
 93         for(i=0;i<n;i++)
 94         {
 95             st=lower_bound(x,x+k,p[i].left)-x;
 96             en=lower_bound(x,x+k,p[i].right)-x;
 97             Update(st,en,p[i].color,0,k-1,1);
 98         }
 99         memset(vis,false,sizeof(vis));
100         Query(0,k-1,1);
101         st=-1;
102         en=-2;
103         x[k]=x[k-1]+1;
104         for(i=0;i<k;i++)
105         {
106             if(vis[i])
107             {
108                 for(j=i;vis[j]&&j<k;j++);
109                 j--;
110                 if(en-st<x[j+1]-1-x[i])
111                 {
112                     en=x[j+1]-1;
113                     st=x[i];
114                 }
115                 i=j;
116             }
117         }
118         if(st<0)
119             puts("Oh, my god");
120         else
121             printf("%d %d\n",st,en);
122     }
123     return 0;
124 }
新博客：www.zhixiangli.com