1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
| #include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std;
#define DB double
const int CN = 110; const DB EPS = 1e-7;
int Q;
int H = 101,A = 1001;
DB d[4*CN][4*CN*10]; void build(){ for(int i=1;i<=4*H;i++) for(int j=1;j<=4*A;j++) d[i][j] = -1; } void sub_modify(int sl,int sr,int sk,int fk,int sa,DB sL){ if(sl == sr) return (void)(d[fk][sk] = max(d[fk][sk], sL)); int sm = (sl+sr)>>1; if(sa <= sm) sub_modify(sl,sm,sk<<1,fk,sa,sL); if(sm < sa) sub_modify(sm+1,sr,sk<<1|1,fk,sa,sL); d[fk][sk] = max(d[fk][sk<<1], d[fk][sk<<1|1]); } void modify(int l,int r,int k,int h,int a,DB L){ sub_modify(1,A,1,k,a,L); if(l == r) return; int m = (l+r)>>1; if(h <= m) modify(l,m,k<<1,h,a,L); if(m < h) modify(m+1,r,k<<1|1,h,a,L); } DB sub_query(int sl,int sr,int sk,int fk,int sas,int sat){ if(sas<=sl && sr<=sat) return d[fk][sk]; int sm = (sl+sr)>>1; DB srec = -1; if(sas <= sm) srec = max(srec, sub_query(sl,sm,sk<<1,fk,sas,sat)); if(sm < sat) srec = max(srec, sub_query(sm+1,sr,sk<<1|1,fk,sas,sat)); return srec; } DB query(int l,int r,int k,int hs,int ht,int as,int at){ if(hs<=l && r<=ht) return sub_query(1,A,1,k,as,at); int m = (l+r)>>1; DB rec = -1; if(hs <= m) rec = max(rec, query(l,m,k<<1,hs,ht,as,at)); if(m < ht) rec = max(rec, query(m+1,r,k<<1|1,hs,ht,as,at)); return rec; }
int main() { scanf("%d",&Q); while(Q){ build(); while(Q--){ char c; cin>>c; if(c == 'I'){ int h; DB a,l; scanf("%d%lf%lf",&h,&a,&l); (a *= 10) += 1; h -= 99; modify(1,H,1,h,(int)a,l); } else{ int h1,h2; DB a1,a2; scanf("%d%d%lf%lf",&h1,&h2,&a1,&a2); if(h1 > h2) swap(h1,h2); if(a1 > a2) swap(a1,a2); h1 -= 99; h2 -= 99; (a1 *= 10) += 1; (a2 *= 10) += 1; DB ans = query(1,H,1,h1,h2,(int)a1,(int)a2); if(ans < -EPS) printf("-1\n"); else printf("%.1lf\n",ans); } } scanf("%d",&Q); } return 0; }
|