蒟蒻求助
查看原帖
蒟蒻求助
501923
duchengjun楼主2021/10/10 11:50
#include<bits/stdc++.h>
using namespace std;
long long n;
long long a[16000010],cnt=0;
long long x[4010],y[4010],u[4010],v[4010],s=0;
int bs1(long long t,long long s){
	long long l=1,r=s+1;
	while(l<r){
		int m=(l+r)>>1;
		if(a[m]>=t)r=m;
		else l=m+1;
	}
	return l;
}
int bs2(long long t,long long s){
	long long l=1,r=s+1;
	while(l<r){
		int m=(l+r)>>1;
		if(a[m]>t)r=m;
		else l=m+1;
	}
	return l;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
    int T;
    cin>>T;
    while(T--){
    	memset(x,0,sizeof(x));
    	memset(y,0,sizeof(y));
    	memset(u,0,sizeof(u));
    	memset(v,0,sizeof(v));
    	memset(a,0,sizeof(a));
    	cnt=0,s=0;
	    cin>>n;
    	for(int i=1;i<=n;i++)
    		cin>>x[i]>>y[i]>>u[i]>>v[i];
	    for(int i=1;i<=n;i++)
	    	for(int j=1;j<=n;j++)
	    		a[++s]=x[i]+y[j];
    	sort(a+1,a+1+s);
    	for(int i=1;i<=n;i++)
	    	for(int j=1;j<=n;j++)
	    		cnt+=bs2(-(u[i]+v[j]),s)-bs1(-(u[i]+v[j]),s);
    	cout<<cnt<<endl<<endl;
    }
}
2021/10/10 11:50
加载中...