Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

為啥我MLE?????

Posted by OYBDOOO at 2019-08-02 16:46:29 on Problem 1151
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator