为什么最后一个点A了,结果前面5个点都MLE了???
查看原帖
为什么最后一个点A了,结果前面5个点都MLE了???
344382
lmrttx楼主2020/11/22 10:21

题目是扫描线,看清月的博客学习的。为什么MLE了5个点,样例还没输出???求助,谢谢。

#include<bits/stdc++.h>
#define  lson id<<1
#define  rson id<<1|1
#define mid (l+r)>>1
using namespace std;
struct edge{
int left,right,height,flag;
}e[100005];
struct segtree{
    int sum,num,len;
    bool lflag,rflag;
}tree[1000010];
int n,max_=-2147483647,min_=2147483647,cnt,ans,last;

void add1(int l,int r,int h,int f){
    e[++cnt].left=l;
    e[cnt].right=r;
    e[cnt].height=h;
    e[cnt].flag=f;
    }

bool cmp(edge x,edge y){return x.height<y.height||x.height==y.height&&x.flag>y.flag;}

void pushup(int id,int l,int r){
if(tree[id].sum)
	{
		tree[id].num=1;
		tree[id].len=r-l+1;
		tree[id].lflag=tree[id].rflag=1;
	}
	else if(l==r)
	{
		tree[id].len=0;
		tree[id].num=0;
		tree[id].lflag=tree[id].rflag=0;
	}
	else
	{
		tree[id].len=tree[lson].len+tree[rson].len;
		tree[id].num=tree[lson].num+tree[rson].num;
		if(tree[lson].rflag&&tree[rson].lflag)tree[id].num--;
		tree[id].lflag=tree[lson].lflag;
		tree[id].rflag=tree[rson].rflag;
	}
}    

void add2(int id,int l,int r,int from,int to,int value)
{
	if(l>=from&&r<=to)
	{
		tree[id].sum+=value;
		pushup(id,l,r);
		return;
	}
	if(from<=mid) add2(lson,l,mid,from,to,value);
	if(to>mid) add2(rson,mid+1,r,from,to,value);
	pushup(id,l,r);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    max_=max(max_,max(x1,x2));min_=min(min_,min(x1,x2));
    add1(x1,x2,y1,1);add1(x1,x2,y2,-1);
    }
    if(min_<=0){
    for(int i=1;i<=cnt;i++){
    e[i].left+=-min_+1;e[i].right+=-min_+1;}
    max_-=min_;
    }
    sort(e+1,e+cnt+1,cmp);
    for(int i=1;i<=cnt;i++){
    add2(1,1,max_,e[i].left,e[i].right-1,e[i].flag);
    while(e[i].height==e[i+1].height&&e[i].flag==e[i+1].flag)
    {i++;add2(1,1,max_,e[i].left,e[i].right-1,e[i].flag);}
    ans+=abs(tree[1].len-last);
	last=tree[1].len;
    ans+=tree[1].num*2*(e[i+1].height-e[i].height);
    }
    printf("%d\n",ans);
    return 0;
}

2020/11/22 10:21
加载中...