HDU 1199 Color the Ball

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 100001;
 4 int tree[maxn<<2],d[maxn<<2],x[maxn],y[maxn],tot;
 5 bool color[maxn],wb[maxn];
 6 inline void pushdown(int v) {
 7     tree[v<<1] = tree[v<<1|1] = tree[v];
 8     tree[v] = -1;
 9 }
10 inline void pushup(int v) {
11     if(tree[v<<1] == tree[v<<1|1])
12         tree[v] = tree[v<<1];
13     else tree[v] = -1;
14 }
15 void update(int L,int R,int lt,int rt,int val,int v) {
16     if(lt <= L && rt >= R) {
17         tree[v] = val;
18         return;
19     }
20     int mid = (L + R)>>1;
21     if(tree[v] >= 0) pushdown(v);
22     if(lt < mid) update(L,mid,lt,rt,val,v<<1);
23     if(rt > mid) update(mid,R,lt,rt,val,v<<1|1);
24     pushup(v);
25 }
26 void query(int L,int R,int v) {
27     if(tree[v] >= 0) {
28         for(int i = L; tree[v]&&i < R; ++i)
29             color[i] = true;
30         return;
31     }
32     //if(R >= L) return;
33     if(tree[v] >= 0) pushdown(v);
34     int mid = (L + R)>>1;
35     query(L,mid,v<<1);
36     query(mid,R,v<<1|1);
37 }
38 int main() {
39     int n;
40     char op[3];
41     while(~scanf("%d",&n)){
42         memset(tree,0,sizeof tree);
43         memset(color,false,sizeof color);
44         memset(wb,false,sizeof wb);
45         for(int i = tot = 0; i < n; ++i){
46             scanf("%d%d%s",x+i,y+i,op);
47             wb[i] = *op == ‘w‘;
48             y[i]++;
49             d[tot++] = x[i];
50             d[tot++] = y[i];
51         }
52         sort(d,d+tot);
53         tot = unique(d,d+tot) - d;
54         for(int i = 0; i < n; ++i){
55             int nx = lower_bound(d,d+tot,x[i])-d;
56             int ny = lower_bound(d,d+tot,y[i])-d;
57             update(0,tot,nx,ny,wb[i],1);
58         }
59         query(0,tot,1);
60         int i = 0,j = 0,ret = 0,L = 0,R = 0;
61         while(i < tot && j < tot){
62             if(color[i]){
63                 j = i;
64                 while(i < tot && color[i]) ++i;
65                 if(d[i] - d[j] + 1 > ret){
66                     ret = d[i] - d[j];
67                     L = d[j];
68                     R = d[i]-1;
69                 }
70             }
71             i++;
72         }
73         if(L >= R) puts("Oh, my god");
74         else printf("%d %d\n",L,R);
75     }
76     return 0;
77 }