1 #include"iostream"  2 #include"cstdio"  3 #include"cstring"  4 #include"algorithm"  5 using namespace std;  6 struct seg_ment_node  7 {  8     int al;  9     int ar; 10     double dl; 11 }; 12 struct seg_ment_tree 13 { 14     int hl; 15     int hr; 16     struct seg_ment_node next[2100]; 17 }node[300]; 18 #define eps 1e-6 19 void creat_tree(int p,int hll,int hrr); 20 void creat_node(int p,int pp,int all,int arr); 21 void init(); 22 void insert_h(int p,int h,int a,double l); 23 void insert_a(int p,int pp,int a,double l); 24 double search_h(int p,double hl,double hr,double al,double ar); 25 double search_a(int p,int pp,double al,double ar); 26 int main() 27 { 28     int m; 29     int h; 30     double a,l; 31     double hl,hr,al,ar; 32     double hhl,hhr,aal,aar; 33     char oper; 34     creat_tree(1,100,200); 35     while(scanf("%d",&m)==1) 36     { 37         if(m==0) 38             break; 39         init(); 40         while(m--) 41         { 42             getchar(); 43             scanf("%c",&oper); 44             if(oper==‘I‘) 45             { 46                 scanf("%d%lf%lf",&h,&a,&l); 47                 insert_h(1,h,(int)(a*10+0.1),l); 48             } 49             else if(oper==‘Q‘) 50             { 51                 scanf("%lf%lf%lf%lf",&hl,&hr,&al,&ar); 52                 if(hl>hr) 53                     swap(hl,hr); 54                 if(al>ar) 55                     swap(al,ar); 56                 double ans=search_h(1,hl,hr,al*10,ar*10); 57                 if(ans>=0) 58                     printf("%.1lf\n",ans); 59                 else 60                     puts("-1"); 61             } 62         } 63     } 64     return 0; 65 } 66 void init() 67 { 68     for(int i=0;i<300;i++) 69         for(int j=0;j<2100;j++) 70         { 71             node[i].next[j].dl=-1; 72         } 73     return ; 74 }  75 void creat_tree(int p,int hll,int hrr) 76 { 77     node[p].hl=hll; 78     node[p].hr=hrr; 79     creat_node(p,1,0,100); 80     if(hll==hrr) 81         return ; 82     int mid=(hll+hrr)/2; 83     creat_tree(p*2,hll,mid); 84     creat_tree(p*2+1,mid+1,hrr); 85     return ; 86 }  87 void creat_node(int p,int pp,int all,int arr) 88 { 89     node[p].next[pp].al=all; 90     node[p].next[pp].ar=arr; 91     if(all==arr) 92         return ; 93     int mid=(all+arr)/2; 94     creat_node(p,pp*2,all,mid); 95     creat_node(p,pp*2+1,mid+1,arr); 96     return ; 97 } 98 void insert_h(int p,int h,int a,double l) 99 {100     insert_a(p,1,a,l);101     if(node[p].hl==node[p].hr)102         return ;103     int mid=(node[p].hl+node[p].hr)/2;104     if(h<=mid)105         insert_h(p*2,h,a,l);106     else107         insert_h(p*2+1,h,a,l);108     return ;109 }110 void insert_a(int p,int pp,int a,double l)111 {112     if(node[p].next[pp].dl<l)113         node[p].next[pp].dl=l;114     if(node[p].next[pp].al==node[p].next[pp].ar)115         return ;116     int mid=(node[p].next[pp].al+node[p].next[pp].ar)/2;117     if(a<=mid)118         insert_a(p,pp*2,a,l);119     else120         insert_a(p,pp*2+1,a,l);121     return ;122 }123 double search_h(int p,double hl,double hr,double al,double ar)124 {125     double ans=-1;126     if(hl<=node[p].hl&&node[p].hr<=hr)127         return search_a(p,1,al,ar);128     if(node[p].hl==node[p].hr)129         return ans;130     int mid=(node[p].hl+node[p].hr)/2;131     if(hl<=mid)132         ans=max(ans,search_h(p*2,hl,hr,al,ar));133     if(hr>mid)134         ans=max(ans,search_h(p*2+1,hl,hr,al,ar));135     return ans;136 }137 double search_a(int p,int pp,double al,double ar)138 {139     double ans=-1;140     if(al<=node[p].next[pp].al&&node[p].next[pp].ar<=ar)141         return node[p].next[pp].dl;142     if(node[p].next[pp].al==node[p].next[pp].ar)143         return ans;144     int mid=(node[p].next[pp].al+node[p].next[pp].ar)/2;145     if(al<=mid)146         search_a(p,pp*2,al,ar);147     if(ar>mid)148         search_a(p,pp*2+1,al,ar);149     return ans;150 }