Submission #56575494

---

Source Code Expand

#include<bits/stdc++.h>
#define lc(p) ((p)*2)
#define rc(p) ((p)*2+1)
#define mkpr make_pair
#define LL long long
using namespace std;
inline LL read() {
    char ch=getchar();
    LL x=0;
    bool t=0;
    while(ch<'0'||ch>'9')   t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return t?-x:x;
}
int n,d,a[200005],b[200005];
LL x[4000006],y[4000006];
LL ans,s[200005];
const int N=2000000;
int main(){
	n=read();
	d=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		b[i]=read();
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++){
		s[i]=s[i-1]+a[i];
	}
	for(int i=-N;i<=N;i++){
		int pos=lower_bound(a+1,a+1+n,i)-a;
		x[i+N]=s[n]-s[pos-1]-1ll*(n-pos+1)*i+1ll*(pos-1)*i-s[pos-1];
	}
	for(int i=1;i<=n;i++){
		s[i]=s[i-1]+b[i];
	}
	for(int i=-N;i<=N;i++){
		int pos=lower_bound(b+1,b+1+n,i)-b;
		y[i+N]=s[n]-s[pos-1]-1ll*(n-pos+1)*i+1ll*(pos-1)*i-s[pos-1];
	}
	sort(x,x+1+N*2);
	for(int i=-N;i<=N;i++){
		int pos=upper_bound(x,x+1+N*2,d-y[i+N])-x;
		ans+=pos;
	}
	cout<<ans;
	return 0;
}

Submission Info

Judge Result