求助,和标程一模一样(几乎),可交上后总是听取WA声一片
查看原帖
求助,和标程一模一样(几乎),可交上后总是听取WA声一片
184055
Beyond616楼主2020/8/3 11:41
#include <algorithm>
#include <cstring>
#include <cstdio>
#define ll long long
#define N (ll) 1e5+23
#define lson (now<<1)
#define rson ((now<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
struct line
{
	ll l,r,mark,h;
	bool operator < (const line &x) const
	{
		return h < x.h;
	} 
}l[N<<1];
struct Tree
{
	ll l,r,sum,len;
}tree[N<<2];
ll X[N*2],n,x1,x2,y1,y2,tot,ans;
void push_up(ll now)
{
	ll l=tree[now].l,r=tree[now].r;
	if (tree[now].sum)
	tree[now].len=X[r+1]-X[l];
	else tree[now].len=tree[lson].len+tree[rson].len;
}
void build(ll now,ll l,ll r)
{
	tree[now].l=l;
	tree[now].r=r;
	tree[now].len=tree[now].sum=0;
	if (l==r) return;
	build(lson,l,mid);
	build(rson,mid+1,r);
}
void updata(ll now,ll L,ll R,ll c)
{
	ll l=tree[now].l,r=tree[now].r;
	if (X[l]>=R||X[r+1]<=L) return;
	if (L<=X[l]&&X[r+1]<=R)
	{
		tree[now].sum+=c;
		push_up(now);
		return;
	}
	updata(lson,L,R,c);
	updata(rson,L,R,c);
	push_up(now);
}
int main()
{
	scanf("%lld",&n);
	memset(X,0,sizeof(X));
	for (ll i=1;i<=n;++i)
	{
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		X[i*2-1]=x1; X[i*2]=x2;
		l[i*2-1]=(line){x1,x2,1,y1};
		l[i*2]=(line){x1,x2,-1,y2};
	}
	sort(l+1,l+2*n+1);
	sort(X+1,X+2*n+1);
	tot=unique(X+1,X+2*n+1)-X-1;
	build(1,1,tot-1);
	for (ll i=1;i<n*2;++i)
	{
		updata(1,l[i].r,l[i].r,l[i].mark);
		ans+=tree[1].len*(l[i+1].h-l[i].h);
	}
	printf("%lld",ans);
}
2020/8/3 11:41
加载中...