#pragma optimze("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
// #define endl '\n'
const int N=76;
int pre[N][N][N];
// bool have1[N];
bitset<100> have1;
int have3[N][N][N];
int main()
{
ios::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int b,m;
cin>>b;
if(b==1)
{
int n,d;
cin>>n>>d>>m;
vector<int> a;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a.push_back(x);
}
long long cnt=0;
sort(begin(a),end(a));
int i=0;
for(int j=0;j<n;j++)
{
while(i<n and a[i]<(a[j]-d))
{
i++;
}
cnt+=(j-i);
}
cout<<cnt<<'\n';
}
else if(b==2)
{
// exit(-1);
int n,d;
cin>>n>>d>>m;
long long ap1=n;
ap1*=ap1;
long long kp=(2e8);
if(ap1<=kp)
{
vector<pair<int,int>> a;
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
a.push_back({x,y});
}
long long cnt=0;
for(int i=0;i<n;i++)
{
for(int k=i+1;k<n;k++)
{
if((abs(a[i].first-a[k].first)+abs(a[i].second-a[k].second))<=d)
{
cnt++;
}
}
}
cout<<cnt<<'\n';
exit(0);
}
vector<pair<int,int>> a;
vector<vector<int>> pre1;
vector<int> ap;
// for(int i=0;i<=m;i++)
// ap.push_back(0);
for(int j=0;j<=m;j++)
pre1.push_back(ap);
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
a.push_back({x,y});
while(pre1[x].size()<=m)
{
pre1[x].push_back(0);
}
while(y<=m)
{
pre1[x][y]++;
y++;
}
}
long long cnt=0;
for(int i=0;i<n;i++)
{
int x=a[i].first;
int y=a[i].second;
for(int dx=0;dx<=d and dx<=(m-1);dx++)
{
int dy=d-dx;
if((x+dx)<=m and pre1[x+dx].size()>0)
{
cnt+=(pre1[(x+dx)][min(m,y+dy)]-pre1[x+dx][max(0,y-dy-1)])-(dx==0);
}
if((x-dx)>0 and dx!=0 and pre1[x-dx].size()>0)
{
cnt+=(pre1[(x-dx)][min(m,y+dy)]-pre1[x-dx][max(0,y-dy-1)]);
}
}
// cout<<"For "<<i<<' '<<cnt<<endl;
}
cout<<cnt/2<<'\n';
}
else
{
int n,d;
cin>>n>>d>>m;
long long ap1=n;
ap1*=ap1;
long long kp=(2e8);
if(ap1<=kp)
{
vector<vector<int>> a;
for(int i=0;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
a.push_back({x,y,z});
}
long long cnt=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if((abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1])+abs(a[i][2]-a[j][2]))<=d)
{
cnt++;
}
}
}
cout<<cnt<<'\n';
exit(0);
}
vector<pair<int,pair<int,int>>> a;
for(int i=0;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
a.push_back({x,{y,z}});
have1[x]=1;
have3[x][y][z]++;
while(z<=m)
{
pre[x][y][z]++;
z++;
}
}
long long cnt=0;
d=min(d,(m-1)*b);
sort(begin(a),end(a));
a.resize(unique(begin(a),end(a))-begin(a));
for(int i=0;i<a.size();i++)
{
int x=a[i].first,y=a[i].second.first,z=a[i].second.second;
int p=0;
for(int dx=0;dx<=(d) and dx<=(m-1);dx++)
{
if((x+dx>m or !have1[x+dx]) and ((x-dx)<=0 or !have1[x-dx]))
continue;
for(int dy=0;dy<=(m-1) and dy<=d and (dy+dx)<=d and (dy+dx)<=(2*(m-1));dy++)
{
int dz=d-(dy+dx);
if((x+dx)<=m)
{
if((y+dy)<=m)
{
p+=(pre[x+dx][y+dy][min(m,z+dz)]-pre[x+dx][y+dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
}
if((y-dy)>0 and (dy!=0))
{
p+=(pre[x+dx][y-dy][min(m,z+dz)]-pre[x+dx][y-dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
}
}
if((x-dx)>0 and (dx!=0))
{
if((y+dy)<=m)
{
p+=(pre[x-dx][y+dy][min(m,z+dz)]-pre[x-dx][y+dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
}
if((y-dy)>0 and (dy!=0))
{
p+=(pre[x-dx][y-dy][min(m,z+dz)]-pre[x-dx][y-dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
}
}
}
}
cnt+=p*have3[x][y][z];
}
cout<<cnt/2<<'\n';
}
return 0;
}
Compilation message
pairs.cpp:1: warning: ignoring '#pragma optimze ' [-Wunknown-pragmas]
1 | #pragma optimze("Ofast")
|
pairs.cpp: In function 'int main()':
pairs.cpp:87:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
87 | while(pre1[x].size()<=m)
| ~~~~~~~~~~~~~~^~~
pairs.cpp:166:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for(int i=0;i<a.size();i++)
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
1504 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
1504 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1756 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
1508 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1504 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
2256 KB |
Output is correct |
| 2 |
Correct |
47 ms |
2260 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
200 ms |
6348 KB |
Output is correct |
| 2 |
Correct |
450 ms |
6180 KB |
Output is correct |
| 3 |
Correct |
369 ms |
5836 KB |
Output is correct |
| 4 |
Correct |
427 ms |
6092 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
815 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
4820 KB |
Output is correct |
| 2 |
Correct |
23 ms |
4820 KB |
Output is correct |
| 3 |
Correct |
22 ms |
4820 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
63 ms |
6100 KB |
Output is correct |
| 2 |
Correct |
632 ms |
5840 KB |
Output is correct |
| 3 |
Correct |
958 ms |
5840 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
353 ms |
6096 KB |
Output is correct |
| 2 |
Correct |
1464 ms |
6100 KB |
Output is correct |
| 3 |
Correct |
1775 ms |
6100 KB |
Output is correct |
