提出 #73073394

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
const int MAXN=400005,V=1000000000;
int read() {
	static int c=getchar(),f=1,x=0;
	for(f=1; c<48||c>57; c=getchar())f=f&&c^45;
	for(x=0; c>47&&c<58; c=getchar())x=(x<<3)+(x<<1)+(c&15);
	return f?x:-x;
}
int a[MAXN],n,d,rt[MAXN],tcnt;
struct Tree {
	int ls,rs,cnt;
} tr[MAXN*80];
void update(int&num,int pre,int l,int r,int x) {
	if(!num||num==pre) num=++tcnt,tr[num]=tr[pre];
	++tr[num].cnt;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(x<=mid) return update(tr[num].ls,tr[pre].ls,l,mid,x);
	return update(tr[num].rs,tr[pre].rs,mid+1,r,x);
}
int query(int num,int pre,int l,int r,int L,int R) {
	if(L<=l&&r<=R) return tr[num].cnt-tr[pre].cnt;
	int mid=(l+r)>>1;
	if(R<=mid) return query(tr[num].ls,tr[pre].ls,l,mid,L,R);
	if(mid<L)return query(tr[num].rs,tr[pre].rs,mid+1,r,L,R);
	return query(tr[num].ls,tr[pre].ls,l,mid,L,mid)+query(tr[num].rs,tr[pre].rs,mid+1,r,mid+1,R);
}
int main() {
	n=read(),d=read();
	for(int i=1; i<=n; ++i) a[i]=read(),rt[i]=rt[i-1],update(rt[i],rt[i-1],1,V,a[i]);
	long long ans=0;
	for(int r=1,l=1; r<=n; ++r) {
//		cout<<query(rt[r-1],rt[l-1],1,V,max(1,a[r]-d+1),min(V,a[r]+d-1))<<endl;
		while(l<r&&query(rt[r-1],rt[l-1],1,V,max(1,a[r]-d+1),min(V,a[r]+d-1))) ++l;
		ans+=r-l+1;
	}
	printf("%lld\n",ans);
	return 0;
}

提出情報

ジャッジ結果