样例WA,求调
查看原帖
样例WA,求调
1124941
woden楼主2025/8/28 22:34
#include<bits/stdc++.h>
#define int long long
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=1e5+99;
int n;
struct node{
	int x,y1,y2,k;
}l[N<<1];
int y[N<<1],m;
int cnt[N<<3],len[N<<3];
void pushup(int rt,int l,int r){
	int ls=rt<<1,rs=rt<<1|1;
	if(cnt[rt]){
		len[rt]=y[r+1]-y[l];
	}else if(l==r){
		len[rt]=0;
	}else{
		len[rt]=len[ls]+len[rs];
	}
}
void update(int rt,int l,int r,int ql,int qr,int k){
	int ls=rt<<1,rs=rt<<1|1;
	if(ql<=l&&r<=qr){
		cnt[rt]+=k;
		pushup(rt,l,r);
		return;
	}
	int mid=l+r>>1;
	if(ql<=mid){
		update(ls,l,mid,ql,qr,k);
	}
	if(mid<qr){
		update(rs,mid+1,r,ql,qr,k);
	}
	pushup(rt,l,r);
}
signed main() {
	fst;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;
		l[i<<1]={x1,y1,y2,1};
		l[i<<1|1]={x2,y1,y2,-1};
		y[i<<1]=y1;
		y[i<<1|1]=y2;
	}
	sort(y+1,y+n*2+1);
	m=unique(y+1,y+n*2+1)-y-1;
	y[m+1]=y[m];
	for(int i=1;i<=n*2;i++){
		l[i].y1=lower_bound(y+1,y+1+m,l[i].y1)-y;
		l[i].y2=lower_bound(y+1,y+1+m,l[i].y2)-y;
	}
	sort(l+1,l+1+n*2,[](node a,node b){
		return a.x<b.x;
	});
	int ans=0;
	for(int i=1;i<=n*2;i++){
		if(i>1) ans+=len[1]*(l[i].x-l[i-1].x);
		if(l[i].y1<l[i].y2) update(1,0,m-1,l[i].y1,l[i].y2-1,l[i].k);
	}
	cout<<ans<<endl;
	return 0;
}
2025/8/28 22:34
加载中...