/*
..
.:^!7?JJJYJJJJ?77!!~^.
.:~7JYYJYYJJ?77?J??JY?JYY5YY?7~:.
:!J5YJ??777J?J?????7J?J?7J?J?JYYYYY?~.
:?5JJ???77!?77?J??J7?7???JJJJ?J777??JYJY?!.
^J5YYJJJ77?!7!7!77JJJJ?J77??Y???77!!777!7?JY5?^
~JYY??J7??7J?7?!7!7???J?77!777J?JY?J7777?7?????5PY^
^Y5J??J??!!???J??77777????J?J77?YY?!~^::::::^!77??YPG7.
!PY?777?77!7!7J?7!7?????JJ??7J??J^:. .:!7?75GY:
.JPJ!7!7?7?7!7!????????J?7??7J?YJ~. .:!7?JGP^
.JP?!7!!??7J7!!!?7J????7J7!!?!?7?7. . ^??YG5:
!P??7777?77??777?7?!7!777!?7J??J?^ :~~: . ^?7YGY.
:PY7??77!7~~:::.....:^^~!7??????J?^ . .7PGGPY: . !?JPB~
.Y5!!Y77!~:.. .:~7JJJ??J!. . . .5GGGGP^ ..:J?JBJ
~G?!!?7!^. .^7JJYYJ7:. . ..:~???~^^:..77?G5.
!G!7?77: ..?J7~^~!77: . .. ..^~~~~~~~:.!75B!
!P77J7^ ..~?:::^~!7?^ ........^~^^^^^:.^JYG?.
!G???!: .~77!:. ..7?7?77~:....................^JPJ~
:P5??7: .JGGGGP! ...... ..................:^!JP?^
7BJ7J~ .JGGGGG~ . .....................::::^!7?JJ?!^.
.YG?Y7^ .~7??~:::. .. .... ... ....::::::::::::^?~^!?J7:
:PPJ??: ..:^^^^^^: . .... ....::::^::::::::.:::^JP~..:75~
:YGYJ?^. .^^^^^^^:. .....:::::::::::...:::..:.::JP!~~7Y~
~PP5J?^...::::.... ......::::::::.:.::.:::::.:::::::::^JP?7~.
:75P5YJ!~^^^^!:...::^:::::::...:......::.....::::::::^^5?
?G?Y55PP5YJ!^:::::::::..:..:.:....:...:....::..::::^^7G^
~P!^:::::.::::::::::::::...:.::::.:.:::::.:.......:::^PY
:!JJ7~^::::::::::::::::..:.:.::.:::::...::.........:.JP.
:5P?^:^:::::^::::::::::::.::::::.:.::.::........::7P:
.P7::::::::::^::^^::::::::::::::::.:.........:::::J5.
. ^G~:^^:::::::^:^^^^^:::::::::^:::::::::::::::^^::75^
:P!^^^^^^^^:^^^^^^:^:::::^:::^:::::::::::::::^^7JY^
.!5~^~^^^^^^^^^:^^^^^^^^:^^^^:^^^^^^^^^^^^^^~?55G?
~J?~~~^^~~^~~~^^^^^^^:^^^~^^^^^^^^~~!!!?Y55GP?J!.
.~PYJ?77?7777!!!!!!!!!!!!7777??JJJJJ5PP5??J^ ..
.777?5J??YYYYY5?7777!!!!~!~~^^::. .::
:!!~:.:^^:
PENGUIN SO CUTE, I LOVE PENGUIN
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define NAME "disrupt"
#define int long long
#define pii pair<int,int>
const int oo=1e18;
const int mod=1e9+7;
const int N=1e5;
const int LG=18;
const int Sqrt=350;
//int hx[]={0,0,1,-1,1,1,-1,-1},hy[]={1,-1,0,0,1,-1,1,-1};
int b,n,d,m,bit1[150005],bit2[305][305][305];
void up1(int i,int val)
{
i+=m;
while(i<=2*m)
{
bit1[i]+=val;
i+=i&-i;
}
}
int get1(int i)
{
i+=m;
int g=0;
while(i>0)
{
g+=bit1[i];
i-=i&-i;
}
return g;
}
void up2(int x,int y,int z,int val)
{
for(x+=m*2;x<=4*m;x+=x&-x)
for(int yt=2*m+y;yt<=4*m;yt+=yt&-yt)
for(int zt=2*m+z;zt<=4*m;zt+=zt&-zt)bit2[x][yt][zt]+=val;
}
int get2(int x,int y,int z)
{
int g=0;
for(x+=m*2;x>0;x-=x&-x)
for(int yt=2*m+y;yt>0;yt-=yt&-yt)
for(int zt=2*m+z;zt>0;zt-=zt&-zt)g+=bit2[x][yt][zt];
return g;
}
int sum(int x1,int y1,int z1,int x2,int y2,int z2)
{
return get2(x1,y1,z1)-get2(x2,y1,z1)-get2(x1,y2,z1)-get2(x1,y1,z2)
+get2(x2,y2,z1)+get2(x2,y1,z2)+get2(x1,y2,z2)+get2(x2,y2,z2);
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
//freopen(""NAME".in","r",stdin);
//freopen(""NAME".out","w",stdout);
cin>>b>>n>>d>>m;
if(b==1)
{
int a[N+4];
for(int i=1;i<=n;++i)cin>>a[i];
sort(a+1,a+n+1);
int res=0;
for(int i=1,j=1;i<=n;++i)
{
while(a[i]-a[j]>d&&j<i)++j;
res+=i-j;
}
cout<<res;
return 0;
}
if(b==2)
{
pii a[N+4];
for(int i=1;i<=n;++i)
{
int x,y;cin>>x>>y;
a[i]={x+y,x-y};
}
sort(a+1,a+n+1);
int res=0;
for(int i=1,j=1;i<=n;++i)
{
while(a[i].fi-a[j].fi>d&&j<i)
{
up1(a[j].se,-1);
++j;
}
res+=get1(min(m,a[i].se+d))-get1(max(a[i].se-d-1,-m));
up1(a[i].se,1);
}
cout<<res;
return 0;
}
if(b==3)
{
pair<pii,pii>a[N+4];
for(int i=1;i<=n;++i)
{
int x,y,z;
cin>>x>>y>>z;
a[i]={{x+y+z,x+y-z},{x-y+z,x-y-z}};
}
sort(a+1,a+n+1);
int res=0;
for(int i=1,j=1;i<=n;++i)
{
while(a[i].fi.fi-a[j].fi.fi>d&&j<i)
{
up2(a[j].fi.se,a[j].se.fi,a[j].se.se,-1);
++j;
}
res+=sum(min(2*m,a[i].fi.se+d),min(2*m,a[i].se.fi+d),min(2*m,a[i].se.se+d),
max(-2*m,a[i].fi.se-d-1),max(-2*m,a[i].se.fi-d-1),max(-2*m,a[i].se.se-d-1));
up2(a[i].fi.se,a[i].se.fi,a[i].se.se,1);
}
cout<<res;
return 0;
}
}
/*
ଘ(੭ˊᵕˋ)੭* ੈ✩‧˚huynhyen1609<3
*/
Compilation message
pairs.cpp:95:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
95 | main()
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3412 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
3848 KB |
Output is correct |
| 2 |
Correct |
13 ms |
3796 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
4208 KB |
Output is correct |
| 2 |
Correct |
18 ms |
4204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
4308 KB |
Output is correct |
| 2 |
Correct |
18 ms |
4236 KB |
Output is correct |
| 3 |
Correct |
18 ms |
4308 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4564 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4480 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
4012 KB |
Output is correct |
| 2 |
Correct |
22 ms |
3924 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
4224 KB |
Output is correct |
| 2 |
Correct |
27 ms |
4212 KB |
Output is correct |
| 3 |
Correct |
28 ms |
4216 KB |
Output is correct |
| 4 |
Correct |
25 ms |
4196 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
5628 KB |
Output is correct |
| 2 |
Correct |
31 ms |
5580 KB |
Output is correct |
| 3 |
Correct |
35 ms |
5640 KB |
Output is correct |
| 4 |
Correct |
30 ms |
5608 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
19 ms |
24780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
60 ms |
5276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
217 ms |
40936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
344 ms |
61560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
