【HDOJ】1823 Luck and Love

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 #define MAXN 105
  5 #define MAXM 1005
  6 #define lson l, mid, rt<<1
  7 #define rson mid+1, r, rt<<1|1
  8 
  9 double sons[MAXN<<2][MAXM<<2];
 10 
 11 inline double mymax(double a, double b) {
 12     return (a>b) ? a:b;
 13 }
 14 
 15 inline void PushUP(int rt, int index) {
 16     sons[index][rt] = mymax(sons[index][rt<<1], sons[index][rt<<1|1]);
 17 }
 18 
 19 void build_son(int l, int r, int rt, int index) {
 20     sons[index][rt] = -1;
 21     if (l == r)
 22         return ;
 23     int mid = (l+r)>>1;
 24     build_son(lson, index);
 25     build_son(rson, index);
 26 }
 27 
 28 void build(int l, int r, int rt) {
 29     build_son(0, 1000, 1, rt);
 30     if (l == r)
 31         return ;
 32     int mid = (l+r)>>1;
 33     build(lson);
 34     build(rson);
 35 }
 36 
 37 void Update_son(int l, int r, int rt, int A, double L, int index) {
 38     if (l == r) {
 39         if (L > sons[index][rt])
 40             sons[index][rt] = L;
 41         return ;
 42     }
 43     int mid = (l+r)>>1;
 44     if (A <= mid)
 45         Update_son(lson, A, L, index);
 46     else
 47         Update_son(rson, A, L, index);
 48     PushUP(rt, index);
 49 }
 50 
 51 void Update(int l, int r, int rt, int H, int A, double L) {
 52     Update_son(0, 1000, 1, A, L, rt);
 53     if (l == r)
 54         return ;
 55     int mid = (l+r)>>1;
 56     if (H <= mid)
 57         Update(lson, H, A, L);
 58     else
 59         Update(rson, H, A, L);
 60 }
 61 
 62 double query_son(int ll, int rr, int l, int r, int rt, int index) {
 63     if (ll<=l && rr>=r)
 64         return sons[index][rt];
 65 
 66     int mid = (l+r)>>1;
 67     double max = -1;
 68 
 69     if (ll <= mid)
 70         max = mymax(max, query_son(ll, rr, lson, index));
 71     if (rr > mid)
 72         max = mymax(max, query_son(ll, rr, rson, index));
 73     return max;
 74 }
 75 
 76 double query(int ll, int rr, int l, int r, int rt, int A1, int A2) {
 77     if (ll<=l && rr>=r)
 78         return query_son(A1, A2, 0, 1000, 1, rt);
 79 
 80     int mid = (l+r)>>1;
 81     double max = -1;
 82 
 83     if (ll <= mid)
 84         max = mymax(max, query(ll, rr, lson, A1, A2));
 85     if (rr > mid)
 86         max = mymax(max, query(ll, rr, rson, A1, A2));
 87     return max;
 88 }
 89 
 90 int main() {
 91     int n;
 92     int h1, h2, tmp;
 93     double a, b, c;
 94     char cmd[3];
 95 
 96     while (scanf("%d", &n)!=EOF && n) {
 97         build(100, 200, 1);
 98         while (n--) {
 99             scanf("%s", cmd);
100             if (cmd[0] == ‘I‘) {
101                 scanf("%d %lf %lf", &h1, &a, &b);
102                 Update(100, 200, 1, h1, (int)(a*10), b);
103             } else {
104                 scanf("%d %d %lf %lf", &h1, &h2, &a, &b);
105                 if (h1 > h2) {
106                     tmp = h1;
107                     h1 = h2;
108                     h2 = tmp;
109                 }
110                 if (a > b) {
111                     c = a;
112                     a = b;
113                     b = c;
114                 }
115                 b = query(h1, h2, 100, 200, 1, (int)(a*10), (int)(b*10));
116                 if (b < 0)
117                     printf("-1\n");
118                 else
119                     printf("%.1lf\n", b);
120             }
121         }
122     }
123 
124     return 0;
125 }