WA 求助
查看原帖
WA 求助
285617
黑影洞人楼主2023/3/9 14:33
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 114514
using namespace std;
int n,m,tot,cnt,k,ans;
int e[N],f[N],nn;
void lsh(int *a,int n){
	for(int i=1;i<=n;i++)f[i]=a[i];
	sort(f+1,f+n+1);nn=unique(f+1,f+n+1)-f-1;
}
int getps(int x){return lower_bound(f+1,f+nn+1,x)-f;}
struct node{
	int l,r,x,q,typ;
}q[N],tmp[N];
bool cmpq(node &x,node &y){return x.q^y.q?x.q<y.q:abs(x.typ)<abs(y.typ);}
struct bit{
	int t[N];
	int lowbit(int x){return x&-x;}
	void add(int x,int v){for(int i=x;i<=nn;i+=lowbit(i))t[i]+=v;}
	int query(int x){
		int ans=0;
		for(int i=x;i;i-=lowbit(i))ans+=t[i];
		return ans;
	}
	void update(int x){for(int i=x;i<=nn;i+=lowbit(i))t[i]=0;}
}b;
void cdq(int l,int r){
	if(l==r)return;
	int mid=(l+r)/2;
	cdq(l,mid);cdq(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(q[i].l<=q[j].x){
			if(!q[i].typ)b.add(q[i].x,1);
			tmp[k++]=q[i++];
		}else{
			if(q[j].typ)ans+=(2*b.query(q[j].r)-b.query(q[j].x-1)-b.query(q[j].x))*q[j].typ;
			tmp[k++]=q[j++];
		}
	}
	while(i<=mid){
		if(!q[i].typ)b.add(q[i].x,1);
		tmp[k++]=q[i++];
	}
	while(j<=r){
		if(q[j].typ)ans+=(2*b.query(q[j].r)-b.query(q[j].x-1)-b.query(q[j].x))*q[j].typ;
		tmp[k++]=q[j++];
	}
	for(int i=l;i<=r;i++)if(!q[i].typ)b.update(q[i].x);
	for(int i=l;i<=r;i++)q[i]=tmp[i];
}
signed main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		int x,r,z;
		scanf("%d%d%d",&x,&r,&z);
		e[++cnt]=x-r,e[++cnt]=x+r;
		e[++cnt]=x;
		q[++tot]=(node){x-r,x+r,x,z,0};
		q[++tot]=(node){x-r,x+r,x,z-k-1,-1};
		q[++tot]=(node){x-r,x+r,x,z+k,1};
	}
	lsh(e,cnt);
	for(int i=1;i<=tot;i++){
		q[i].l=getps(q[i].l);
		q[i].r=getps(q[i].r);
		q[i].x=getps(q[i].x);
	}
	sort(q+1,q+tot+1,cmpq);
	cdq(1,tot);
	ans-=n;
	printf("%d",ans>>1);
	return 0;
} 
/*
10 5
41 436 1
478 604 2
169 153 2
358 382 1
334 716 8
500 895 7
724 726 1
464 538 9
962 912 7
467 299 5	
*/
2023/3/9 14:33
加载中...