C++(g++ 7.5.0) 解法, 执行用时: 104ms, 内存消耗: 3616K, 提交时间: 2023-05-10 21:06:08

#include<bits/stdc++.h>
#define int long long
#define maxn 1000100
#define pii pair<int,int>
using namespace std;
int n,d,l,b[maxn];
pii p[maxn];
void add(int x,int w){
    while(x<maxn) b[x]+=w,x+=x&-x;
}
int query(int x){
   int res=0;
   while(x) res+=b[x],x-=x&-x;
   return res;
}
signed main(){
    cin>>n>>d>>l;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        p[i].first=x+y+2*l+1;
        p[i].second=x-y+2*l+1;
    }
    sort(p+1,p+1+n);
    int j=1;
    int ans=0;
    for(int i=1;i<=n;i++){
        while(p[i].first-p[j].first>=d) add(p[j].second,-1),j++;
        ans+=query(min((long long )maxn,p[i].second+d-1))-query(max(0ll,p[i].second-d));
        add(p[i].second,1);
    }
    cout<<n*(n-1)/2-ans<<'\n';
}

C++14(g++5.4) 解法, 执行用时: 91ms, 内存消耗: 2028K, 提交时间: 2019-11-23 11:25:19

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e6+100;
const int fix=5e5+100;

int c[N];

void add(int x,int v)
{
	while(x<N){
		c[x]+=v;
		x+=x&-x;
	}
}
int query(int x){
	int ans=0;
	while(x)
	{
		ans+=c[x];
		x-=x&-x;
	}
	return ans;
}

struct node
{
	int x,y;
	bool operator<(const node &p) const
	{
		return x<p.x;
	};
}q[N];

int main()
{
	ll fk,n,d;
	cin>>n>>d>>fk;d--;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		q[i].x=x+y,q[i].y=x-y+fix;
	}
	sort(q+1,q+1+n);
	int j=1;
	ll ans=n*(n-1)/2;
	for(int i=1;i<=n;i++)
	{
		while(j<i&&q[i].x-q[j].x>d) add(q[j].y,-1),j++;
		ans-=query(q[i].y+d)-query(q[i].y-d-1);//减去不符合的 
		add(q[i].y,1);
	}
	cout<<ans<<endl;
	return 0;
}

C++ 解法, 执行用时: 67ms, 内存消耗: 16888K, 提交时间: 2022-07-13 22:00:00

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
using pii = pair<int, int>;

const int N=2e6+50;

int n, d, L;
pii w[N];

int tr[N];

int lowbit(int x){
	return x&-x;
}

void add(int x, int k){
	for(; x<N; x+=lowbit(x)) tr[x]+=k;
}

int query(int x){
	int res=0;
	for(; x; x-=lowbit(x)) res+=tr[x];
	return res;
}

signed main(){
	cin>>n>>d>>L;
	d=min(d-1, 200000);
	for(int i=1; i<=n; i++){
		int x, y; scanf("%d %d", &x, &y);
		w[i]={x+y, x-y+L+N/4};
	}
	sort(w+1, w+1+n);
	
	long long res=1LL*n*(n-1)>>1;
	for(int i=1, j=1; i<=n; i++){
		while(j<i && w[i].x-w[j].x>d) add(w[j++].y, -1);
		res-=query(w[i].y+d)-query(w[i].y-d-1);
		add(w[i].y, 1);
	}
	cout<<res<<endl;
	return 0;
}