| ||||||||||
| 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