样例过不了,求调!
查看原帖
样例过不了,求调!
866154
fcy20180201楼主2023/9/7 23:00

样例输出 10250,求助大佬!!!

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct SegTree{
	ll cnt,len;
}t[8005];
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
struct sq{
	ll l,r,y,cr;
}ln[2005];
bool cmp(sq xx,sq yy){return xx.y<yy.y;}
int n,x[2005],sx;
ll ans;

void update(int num,int l,int r,int ql,int qr,int c){
	if(qr<x[l] || x[r]<ql)return ;
	if(ql<=x[l] && x[r]<=qr){
		t[num].cnt+=c;
		if(t[num].cnt)t[num].len=x[r]-x[l];
		else t[num].len=t[ls(num)].len+t[rs(num)].len;
		return ;
	}
	int mid=(l+r)>>1;
	update(ls(num),l,mid,ql,qr,c);
	update(rs(num),mid+1,r,ql,qr,c);
	if(t[num].cnt)t[num].len=x[r]-x[l];
	else t[num].len=t[ls(num)].len+t[rs(num)].len;
	return ;	
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		ll xx,xxx,yy,yyy;
		scanf("%lld%lld%lld%lld",&xx,&yy,&xxx,&yyy);
		x[++sx]=xx,x[++sx]=xxx;
		ln[(i<<1)-1]={xx,xxx,yy,1},ln[i<<1]={xx,xxx,yyy,-1};
	}
	n<<=1;
	sort(x+1,x+sx+1);
	sx=unique(x+1,x+sx+1)-x-1;
	sort(ln+1,ln+n+1,cmp);
	for(int i=1;i<n;i++){
		update(1,1,sx,ln[i].l,ln[i].r,ln[i].cr);
		ans+=(ll)(ln[i+1].y-ln[i].y)*t[1].len;
	}
	printf("%lld",ans);
	return 0;
}
2023/9/7 23:00
加载中...