#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,d,m;
void Solve1D(){
vector<int> x(n);
for(int i=0;i<n;i++)scanf("%i",&x[i]);
sort(x.begin(),x.end());
ll ans=0;
for(int i=0;i<n;i++){
int bot=i,top=n-1,pos=i;
while(bot<=top){
int mid=bot+top>>1;
if(x[mid]-x[i]<=d)pos=mid,bot=mid+1;
else top=mid-1;
}
ans+=pos-i;
}
printf("%lld",ans);
}
const int N=200050;
int x[N],y[N],sum[N],dif[N],id[N];
int bit[N];
void Add(int x,int f){for(;x<N;x+=x&-x)bit[x]+=f;}
int Get(int x){int res=0;for(;x;x-=x&-x)res+=bit[x];return res;}
void Solve2D(){
for(int i=0;i<n;i++)scanf("%i%i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i],id[i]=i;
sort(id,id+n,[&](int i,int j){
return dif[i]<dif[j];
});
int j=0;
ll ans=0;
for(int i=0;i<n;i++){
while(dif[id[i]]-dif[id[j]]>d){
Add(sum[id[j]],-1);
j++;
}
ans+=Get(min(N-1,sum[id[i]]+d))-Get(max(1,sum[id[i]]-d-1));
Add(sum[id[i]],1);
}
printf("%lld",ans);
}
const int H=250;
struct BIT3D{
int sum[H][H][H];
void Add(int x,int y,int z,int f){
for(int i=x;i<H;i+=i&-i){
for(int j=y;j<H;j+=j&-j){
for(int k=z;k<H;k+=k&-k){
sum[i][j][k]+=f;
}
}
}
}
int Get(int x,int y,int z){
int res=0;
for(int i=x;i;i-=i&-i){
for(int j=y;j;j-=j&-j){
for(int k=z;k;k-=k&-k){
res+=sum[i][j][k];
}
}
}
return res;
}
int Get(int xl,int xr,int yl,int yr,int zl,int zr){
xl--;yl--;zl--;
xl=max(xl,0);
yl=max(yl,0);
zl=max(zl,0);
xr=min(xr,H-1);
yr=min(yr,H-1);
zr=min(zr,H-1);
return Get(xr,yr,zr)-Get(xl,yr,zr)-Get(xr,yl,zr)-Get(xr,yr,zl)+Get(xl,yl,zr)+Get(xl,yr,zl)+Get(xr,yl,zl)-Get(xl,yl,zl);
}
} ST;
int z[N];
void Solve3D(){
for(int i=1;i<=n;i++)scanf("%i%i%i",&x[i],&y[i],&z[i]),id[i]=i;
sort(id+1,id+n+1,[&](int i,int j){
return x[i]+y[i]+z[i]<x[j]+y[j]+z[j];
});
int j=1;
ll ans=0;
for(int i=1;i<=n;i++){
int l=id[i];
while(x[l]+y[l]+z[l]-x[id[j]]-y[id[j]]-z[id[j]]>d){
int k=id[j];
ST.Add(m-x[k]+y[k]+z[k],m+x[k]-y[k]+z[k],m+x[k]+y[k]-z[k],-1);
j++;
}
ans+=ST.Get(m-x[l]+y[l]+z[l]-d,m-x[l]+y[l]+z[l]+d,m+x[l]-y[l]+z[l]-d,m+x[l]-y[l]+z[l]+d,m+x[l]+y[l]-z[l]-d,m+x[l]+y[l]-z[l]+d);
ST.Add(m-x[l]+y[l]+z[l],m+x[l]-y[l]+z[l],m+x[l]+y[l]-z[l],1);
}
printf("%lld",ans);
}
int main(){
int b;scanf("%i%i%i%i",&b,&n,&d,&m);
if(b==1)Solve1D();
if(b==2)Solve2D();
if(b==3)Solve3D();
}
Compilation message
pairs.cpp: In function 'void Solve1D()':
pairs.cpp:13:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | int mid=bot+top>>1;
| ~~~^~~~
pairs.cpp:7:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
7 | for(int i=0;i<n;i++)scanf("%i",&x[i]);
| ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void Solve2D()':
pairs.cpp:27:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
27 | for(int i=0;i<n;i++)scanf("%i%i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i],id[i]=i;
| ~~~~~^~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'void Solve3D()':
pairs.cpp:79:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
79 | for(int i=1;i<=n;i++)scanf("%i%i%i",&x[i],&y[i],&z[i]),id[i]=i;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:98:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
98 | int b;scanf("%i%i%i%i",&b,&n,&d,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
756 KB |
Output is correct |
2 |
Correct |
20 ms |
748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
748 KB |
Output is correct |
2 |
Correct |
27 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
748 KB |
Output is correct |
2 |
Correct |
26 ms |
768 KB |
Output is correct |
3 |
Correct |
27 ms |
748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
1004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
2284 KB |
Output is correct |
2 |
Correct |
32 ms |
2284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
2284 KB |
Output is correct |
2 |
Correct |
39 ms |
2284 KB |
Output is correct |
3 |
Correct |
42 ms |
2412 KB |
Output is correct |
4 |
Correct |
45 ms |
2284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
2944 KB |
Output is correct |
2 |
Correct |
45 ms |
2924 KB |
Output is correct |
3 |
Correct |
46 ms |
2796 KB |
Output is correct |
4 |
Correct |
52 ms |
2796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
12524 KB |
Output is correct |
2 |
Correct |
8 ms |
12524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
123 ms |
3564 KB |
Output is correct |
2 |
Correct |
113 ms |
3564 KB |
Output is correct |
3 |
Correct |
85 ms |
3568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
327 ms |
19436 KB |
Output is correct |
2 |
Correct |
275 ms |
19308 KB |
Output is correct |
3 |
Correct |
129 ms |
19308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
379 ms |
27500 KB |
Output is correct |
2 |
Correct |
319 ms |
27500 KB |
Output is correct |
3 |
Correct |
173 ms |
27372 KB |
Output is correct |