扫描线样例可过 20pts 求调 orz
查看原帖
扫描线样例可过 20pts 求调 orz
564732
TimSwn090306楼主2023/8/9 15:21

自己造了几组小样例都能过,但是一交就是 WA

有无大佬可以帮忙看一下哪里写错了 (个人实在看不出有啥问题了qwq

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
struct rec{
	int sx,sy,ex,ey;
}a[maxn];
struct line{
	int l,r,y,k;
	inline bool operator < (line tmp) const{
		return y<tmp.y;
	}
}l[maxn<<1];
struct segment{
	int l,r,sum,len;
}c[maxn<<3];
int n,tmp[maxn<<1];
ll ans;
inline void build(int rt,int l,int r){
	c[rt].l=l,c[rt].r=r;
	if (l==r) return ;
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}
inline void upd(int rt,int l,int r,int k){
	if (c[rt].l>r || c[rt].r<l) return ;
	if (c[rt].l>=l && c[rt].r<=r){
		c[rt].sum+=k;
		if (c[rt].sum) c[rt].len=tmp[c[rt].r]-tmp[c[rt].l-1];
		else c[rt].len=c[rt<<1].len+c[rt<<1|1].len;
		return ;
	}
	upd(rt<<1,l,r,k);
	upd(rt<<1|1,l,r,k);
	if (c[rt].sum) c[rt].len=tmp[c[rt].r]-tmp[c[rt].l-1];
	else c[rt].len=c[rt<<1].len+c[rt<<1|1].len;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d%d%d%d",&a[i].sx,&a[i].sy,&a[i].ex,&a[i].ey);
		if (a[i].sx>a[i].ex) swap(a[i].sx,a[i].ex);
		if (a[i].sy<a[i].ey) swap(a[i].sy,a[i].ey);
		tmp[(i<<1)-1]=a[i].sx;
		tmp[i<<1]=a[i].ex;
	}
	sort(tmp+1,tmp+(n<<1)+1);
	int mtot=unique(tmp+1,tmp+(n<<1)+1)-tmp-1;
	for (int i=1;i<=n;i++){
		a[i].sx=lower_bound(tmp+1,tmp+mtot+1,a[i].sx)-tmp;
		a[i].ex=lower_bound(tmp+1,tmp+mtot+1,a[i].ex)-tmp;
	}
	build(1,1,mtot);
	for (int i=1;i<=n;i++){
		l[(i<<1)-1]=(line){a[i].sx,a[i].ex,a[i].sy,-1};
		l[i<<1]=(line){a[i].sx,a[i].ex,a[i].ey,1};
	}
	sort(l+1,l+(n<<1)+1);
	for (int i=1;i<(n<<1);i++){
		upd(1,l[i].l+1,l[i].r,l[i].k);
		ans+=1ll*c[1].len*(l[i+1].y-l[i].y);	
	}
	printf("%lld\n",ans);
	return 0;
}

(悬关

2023/8/9 15:21
加载中...