TLE 求助
查看原帖
TLE 求助
178195
人间温柔楼主2023/1/16 01:32

扫描线模板,我的写法应该已经是正解了,可是3-10全部TLE,是因为常熟太大,还是存在更优解?求助

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=1000005;

int n;
long long x1,x2,y1,y2;
int X[maxn<<1];
long long ans;

inline int read(){
	int ret=0;
	int f=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		ret=ret*10+c-'0';
		c=getchar();
	}
	return ret*f;
}

struct scan_line{
	long long l,r,y;	//扫描线的左端点、右端点和纵坐标 
	int val;			//扫描线的权值(1/-1) 
}l[maxn<<1];

struct segment_tree{
	int l,r;
	int sum;
	long long len;
}t[maxn<<2];

bool cmp(scan_line x,scan_line y){
	return x.y<y.y;
}

void push_up(int pos){
	int l=t[pos].l,r=t[pos].r;
	if(t[pos].sum){
		t[pos].len=X[r+1]-X[l];
	}
	else{
		t[pos].len=t[pos<<1].len+t[pos<<1|1].len;
	}
}

void build(int pos,int l,int r){
	t[pos].l=l; t[pos].r=r;
	if(l==r) return;
	int mid=(l+r)/2;
	build(pos<<1,l,mid);
	build(pos<<1|1,mid+1,r);
	push_up(pos);
}

void modify(int pos,int x,int y,int delta){
	int l=t[pos].l,r=t[pos].r;
	int xl=X[l],xr=X[r+1];
	if(xr<=x || y<=xl) return;
	if(x<=xl && xr<=y){
		t[pos].sum+=delta;
		push_up(pos);
	}
	modify(pos<<1,x,y,delta);
	modify(pos<<1|1,x,y,delta);
	push_up(pos);
}

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		x1=(long long)(read()); y1=(long long)(read()); x2=(long long)(read()); y2=(long long)(read());
		X[2*i-1]=x1; X[2*i]=x2;
		l[2*i-1]=scan_line{x1,x2,y1,1};
		l[2*i]=scan_line{x1,x2,y2,-1};
	}
	n<<=1;
	sort(l+1,l+n+1,cmp);
	sort(X+1,X+n+1);
	int k=unique(X,X+n+1)-X-1;
	
	build(1,1,k-1);
	for(int i=1;i<n;i++){
		modify(1,l[i].l,l[i].r,l[i].val);
		ans+=t[1].len*(l[i+1].y-l[i].y);
	}
	printf("%lld\n",ans);
	return 0;
}
2023/1/16 01:32
加载中...