Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
為啥我MLE?????#include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct DREAM { double l,r,h; int f; }edge[405]; double dian[405]; int lazy[405]; double len[405]; int n; bool cmp(const DREAM&aa,const DREAM&bb) { return aa.h<bb.h; } void psdo(int ll,int rr,int rt) { if(lazy[rt]) len[rt]=dian[rr+1]-dian[ll]; else if(ll==rr) len[rt]=0; else len[rt]=len[rt*2]+len[rt*2+1]; } void upd(int L,int R,int ll,int rr,int rt,int val) { if(L<=ll&&rr<=R) { lazy[rt]+=val; psdo(ll,rr,rt); return; } int mid=(ll+rr)/2; if(L<=mid)upd(L,R,ll,mid,rt*2,val); if(R>mid)upd(L,R,mid+1,rr,rt*2+1,val); psdo(ll,rr,rt); } int tot=0,ttt=0; int nlen; int main() { //freopen("sm.in","r",stdin); //freopen("sm.out","w",stdout); double A,B,C,D; int jvs,i; while(1) { jvs++; scanf("%d",&n); if(n==0)break; printf("Test case #%d\n",jvs); tot=0; ttt=0; for(i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&A,&B,&C,&D); tot++; edge[tot].l=A; edge[tot].r=C; edge[tot].h=B; edge[tot].f=1; tot++; edge[tot].l=A; edge[tot].r=C; edge[tot].h=D; edge[tot].f=-1; ttt++; dian[ttt]=A; ttt++; dian[ttt]=C; } sort(edge+1,edge+tot+1,cmp); sort(dian+1,dian+ttt+1); nlen=unique(dian+1,dian+ttt+1)-dian-1; double ans=0; memset(lazy,0,sizeof(lazy)); memset(len,0,sizeof(len)); for(i=1;i<=tot;i++) { int ll=lower_bound(dian+1,dian+ttt+1,edge[i].l)-dian; int rr=lower_bound(dian+1,dian+ttt+1,edge[i].r)-dian-1; upd(ll,rr,1,nlen,1,edge[i].f); ans+=len[1]*(edge[i+1].h-edge[i].h); } printf("Total explored area: %.2f\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator