求调
查看原帖
求调
905885
Him_shu楼主2024/8/13 20:40
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
#define M 1e6
#define inf 1e14
#define mod 998244353
int n,d;
int x[N],sum_x[N],y[N],sum_y[N],ans,mx,mi;
vector<int>sx,sy;
signed main(){
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	mi=-M*2;
	mx=M*2;
	x[0]=y[0]=mi;
	x[n+1]=y[n+1]=mx;
	sort(x+1,x+n+1);
	sort(y+1,y+n+1);
	for(int i=1;i<=n;i++){
		sum_x[i]=sum_x[i-1]+x[i];
		sum_y[i]=sum_y[i-1]+y[i];
	}
	for(int i=0;i<=n;i++){
		for(int j=x[i];j<x[i+1];j++){
			sx.push_back(i*j-(n-i)*j+((sum_x[n]-sum_x[i])-sum_x[i]));
		}
		for(int j=y[i];j<y[i+1];j++){
			sy.push_back(i*j-(n-i)*j+((sum_y[n]-sum_y[i])-sum_y[i]));
		}
	}
	sort(sx.begin(),sx.end());
	sort(sy.begin(),sy.end());
//	for(auto i:sx){
//		cout<<i<<' ';
//	}
//	cout<<"\n";
//	for(auto i:sy){
//		cout<<i<<" ";
//	}
//	cout<<"\n";
	sy.push_back(inf);
	for(auto i:sx){
		if(d-i<0){
			continue;
		}
//		cout<<(upper_bound(sy.begin(),sy.end(),d-i)-sy.begin())<<" ";
		ans+=(upper_bound(sy.begin(),sy.end(),d-i)-sy.begin());
	}
	cout<<ans;
    return 0;
}
2024/8/13 20:40
加载中...