Submission #76656261

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pb emplace_back
#define pr pair<int,int>
#define mp make_pair
#define endl "\n"
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
const int MAXV=1000005;
int n,d,ans=0;
pr m[300005];
int bitc[MAXV+5],bits[MAXV+5];
int lowbit(int n){return n&-n;}
void add(int q,int v){
	while(q<=MAXV){
		bitc[q]++; 
		bits[q]+=v;
		q+=lowbit(q);
	}
}
int queryc(int q){
	if(q<=0) return 0;
	q=min(q,MAXV);
	int da=0;
	while(q>0){
		da+=bitc[q];
		q-=lowbit(q);
	}
	return da;
}
int querys(int q){
	if(q<=0) return 0;
	q=min(q,MAXV);
	int da=0;
	while(q>0){
		da+=bits[q];
		q-=lowbit(q);
	}
	return da;
}
signed main(){
	n=read();
	d=read();
	for(int i=1;i<=n;i++){m[i].first=read();m[i].second=read();}
	sort(m+1,m+1+n);
	for(int i=1;i<=n;i++){
		int mq=m[i].first+d;
		if(m[i].second>=mq){
			int cnt,sum;
			cnt=queryc(MAXV)-queryc(m[i].second-1);
			ans+=(cnt*(m[i].second-m[i].first-d+1));
			cnt=queryc(m[i].second-1)-queryc(mq-1);
			sum=querys(m[i].second-1)-querys(mq-1);
			ans+=(sum-cnt*(mq-1));
		}
		add(m[i].second,m[i].second);
	}
	cout<<ans;
	return 0;
}

Submission Info

Judge Result