求助,我的代码哪里出问题了,很急
查看原帖
求助,我的代码哪里出问题了,很急
153972
hhdddkk楼主2020/12/4 22:39

全wa

#include<bits/stdc++.h>
using namespace std;
int n,raw[200005],cnt;
long long ans;
struct A{
	int id,val;
}Y[200005];
struct B{
	int x,y,yy,val;
}X[200005];
struct Tree{
	int l,r,cnt,len;
}t[800010];
int Read(){
	int num=0;
	char cc=getchar();
	while(cc<'0'||cc>'9') cc=getchar();
	while(cc>='0'&&cc<='9'){
		num=(num<<1)+(num<<3);
		num+=cc-'0';
		cc=getchar();
	}
	return num;
}
bool cmp(A a,A b){
	return a.val<b.val;
}
bool cmp2(B a,B b){
	return a.x<b.x;
}
void Build(int p,int l,int r){
	t[p].l=l;t[p].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	Build(p<<1,l,mid);
	Build((p<<1)+1,mid+1,r);
}
void Change(int p,int l,int r,int val){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].cnt+=val;
		if(t[p].cnt) t[p].len=raw[t[p].r+1]-raw[t[p].l];
		if(!t[p].cnt) t[p].len=t[p<<1].len+t[(p<<1)+1].len;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) Change(p<<1,l,r,val);
	if(r>mid) Change((p<<1)+1,l,r,val);
	if(t[p].cnt) t[p].len=raw[t[p].r+1]-raw[t[p].l];
	if(!t[p].cnt) t[p].len=t[p<<1].len+t[(p<<1)+1].len;
}
int main(){
	n=Read();
	for(int i=1;i<=n;i++){
		int x=Read(),y=Read(),
		xx=Read(),yy=Read();
		X[i].x=x,X[i].y=y,X[i].yy=yy,X[i].val=1;
		X[i+n].x=xx,X[i+n].y=y,X[i+n].yy=yy,X[i+n].val=-1;
		Y[i].val=y,Y[i].id=i;
		Y[i+n].val=yy,Y[i+n].id=i+n;
	}
	sort(Y+1,Y+2*n+1,cmp);
	for(int i=1;i<=(n<<1);i++){
		if((Y[i].val!=Y[i-1].val)||(i==1)){
			cnt++;
			raw[cnt]=Y[i].val;
		}
		int id=Y[i].id;
		if(id>n){
			X[id-n].yy=cnt;
			X[id].yy=cnt;
		}
		if(id<=n){
			X[id].y=cnt;
			X[id+n].y=cnt;
		}
	}
	Build(1,1,cnt-1);
	sort(X+1,X+2*n+1,cmp2);
	for(int i=1;i<=(n<<1);i++){
		ans=ans+t[1].len*(X[i].x-X[i-1].x);
		Change(1,X[i].y,X[i].yy-1,X[i].val);
	}
	printf("%lld",ans);
	return 0;
}
2020/12/4 22:39
加载中...