ural 1019 Line Painting

http://acm.timus.ru/problem.aspx?space=1&num=1019
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define maxn 200100
  5 using namespace std;
  6 
  7 struct node
  8 {
  9     int r,l,co;
 10 }tree[maxn*4];
 11 int co[maxn],l[maxn],r[maxn];
 12 struct node1
 13 {
 14     int x,y,co;
 15 }p[maxn*4];
 16 
 17 void build(int i,int l,int r)
 18 {
 19     tree[i].l=l;tree[i].r=r;
 20     tree[i].co=1;
 21     if(l==r-1) return ;
 22     int mid=(l+r)>>1;
 23     build(i<<1,l,mid);
 24     build(i<<1|1,mid,r);
 25 }
 26 
 27 void update(int i,int l,int r,int co)
 28 {
 29     if(tree[i].l==l&&tree[i].r==r)
 30     {
 31         tree[i].co=co;
 32         return ;
 33     }
 34     if(tree[i].co>=0&&tree[i].co!=co)
 35     {
 36         tree[i<<1].co=tree[i<<1|1].co=tree[i].co;
 37         tree[i].co=-1;
 38     }
 39     int mid=(tree[i].l+tree[i].r)>>1;
 40     if(r<=mid)
 41     {
 42         update(i<<1,l,r,co);
 43     }
 44     else if(l>=mid)
 45     {
 46         update(i<<1|1,l,r,co);
 47     }
 48     else
 49     {
 50         update(i<<1,l,mid,co);
 51         update(i<<1|1,mid,r,co);
 52     }
 53 }
 54 
 55 void search1(int i,int l,int r)
 56 {
 57     if(tree[i].co>=0)
 58     {
 59         for(int j=tree[i].l; j<tree[i].r; j++)
 60         {
 61             co[j]=tree[i].co;
 62         }
 63         return ;
 64     }
 65     int mid=(tree[i].l+tree[i].r)>>1;
 66     if(r<=mid)
 67     {
 68         search1(i<<1,l,r);
 69     }
 70     else if(l>=mid)
 71     {
 72         search1(i<<1|1,l,r);
 73     }
 74     else
 75     {
 76         search1(i<<1,l,mid);
 77         search1(i<<1|1,mid,r);
 78     }
 79 }
 80 
 81 int bs(int key,int li,int ri)
 82 {
 83     int low=li,high=ri-1;
 84     while(low<=high)
 85     {
 86         int mid=(low+high)>>1;
 87         if(l[mid]==key) return mid;
 88         else if(l[mid]>key)
 89            high=mid-1;
 90         else
 91            low=mid+1;
 92     }
 93 }
 94 
 95 int main()
 96 {
 97     int n;
 98     char ch;
 99     scanf("%d",&n);
100     int cnt=0;
101     for(int i=0; i<=maxn; i++)
102     {
103         co[i]=1;
104     }
105     p[0].x=0;p[0].y=1000000000;
106     l[cnt++]=p[0].x; l[cnt++]=p[0].y;
107     for(int i=0; i<n; i++)
108     {
109         scanf("%d%d %c",&p[i].x,&p[i].y,&ch);
110         l[cnt++]=p[i].x; l[cnt++]=p[i].y;
111         if(ch=='w')
112         {
113             p[i].co=1;
114         }
115         getchar();
116     }
117     sort(l,l+cnt);
118     int t=1;
119     for(int i=1; i<cnt; i++)
120     {
121         if(l[i]!=l[i-1]) l[t++]=l[i];
122     }
123     build(1,0,t);
124     for(int i=0; i<n; i++)
125     {
126         int li=bs(p[i].x,0,t);
127         int ri=bs(p[i].y,0,t);
128         //printf("%d %d
",li,ri);
129         update(1,li,ri,p[i].co);
130     }
131     search1(1,0,t);
132     int s=0,e=0,si,ei;
133     co[t]=0;
134     l[t]=1000000000;
135     for(int i=0; i<t; i++)
136     {
137         si=l[i];
138         while(co[i]==1)
139         i++;
140         ei=l[i];
141         if(ei-si>e-s)
142         {
143             e=ei;
144             s=si;
145         }
146     }
147     printf("%d %d
",s,e);
148     return 0;
149 }
View Code