#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define db long double
#define N 1005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define rand(l,r) (l+rng()%(r-l+1))
using namespace std;
using namespace __gnu_pbds;
struct _1D_Problem
{
ll n,d,x[100005],i,j,res,m;
void Work()
{
cin>>n>>d>>m;
for(i=1;i<=n;i++) cin>>x[i];
sort(x+1,x+n+1);
j=1;
for(i=1;i<=n;i++)
{
while(x[i]-x[j]>d) j++;
res+=i-j;
}
cout<<res;
}
} Line;
struct _2D_Problem
{
typedef tree <II,null_type,less <II>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
struct Fenwick_Tree
{
ordered_set bit[75005];
map <int,int> cnt;
void update(int i,int k)
{
II x={ k,++cnt[k] };
while(i<=75000) bit[i].insert(x),i+=(i & -i);
}
int get(int i,int k)
{
int res=0;
while(i>=1) res+=bit[i].size()-bit[i].order_of_key({ k,0 }),i-=(i & -i);
return res;
}
} SUM,SUB;
II a[100005];
ll n,d,m,i,res;
void Work()
{
cin>>n>>d>>m;
for(i=1;i<=n;i++) cin>>a[i].fst>>a[i].snd;
sort(a+1,a+n+1);
ll res=0;
for(i=1;i<=n;i++)
{
res+=SUM.get(a[i].snd,a[i].fst+a[i].snd-d);
res+=SUB.get(m,a[i].fst-a[i].snd-d)-SUB.get(a[i].snd,a[i].fst-a[i].snd-d);
SUM.update(a[i].snd,a[i].fst+a[i].snd);
SUB.update(a[i].snd,a[i].fst-a[i].snd);
}
cout<<res;
}
} Grid;
struct _3D_Problem
{
struct pt { int x,y,z; } a[100005];
ll res,c[76][76][76];
int f[76][76][76][2*75+1],x,y,z,z1,z2,i,n,m,d,step,sum;
void Work()
{
cin>>n>>d>>m;
for(i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].z;
for(step=1;step<=4;step++)
{
memset(f,0,sizeof(d));
memset(c,0,sizeof(c));
for(i=1;i<=n;i++)
{
f[a[i].z][a[i].x][a[i].y][a[i].x+a[i].y]++;
c[a[i].x][a[i].y][a[i].z]++;
}
for(z=1;z<=m;z++)
for(x=1;x<=m;x++)
for(y=1;y<=m;y++)
for(sum=2*m;sum>=1;sum--)
{
f[z][x][y][sum]+=f[z][x-1][y][sum];
f[z][x][y][sum]+=f[z][x][y-1][sum];
f[z][x][y][sum]+=f[z][x][y][sum+1];
f[z][x][y][sum]-=f[z][x-1][y-1][sum];
f[z][x][y][sum]-=f[z][x][y-1][sum+1];
f[z][x][y][sum]-=f[z][x-1][y][sum+1];
f[z][x][y][sum]+=f[z][x-1][y-1][sum+1];
}
for(z1=1;z1<=m;z1++)
for(z2=1;z2<=z1;z2++)
for(x=1;x<=m;x++)
for(y=1;y<=m;y++)
{
if((z1!=z2 || step<=2) && x+y+z1-z2-d<=2*m)
res+=c[x][y][z1]*f[z2][x-1][y][max(1,x+y+z1-z2-d)];
}
for(i=1;i<=n;i++) swap(a[i].x,a[i].y),a[i].y=m-a[i].y+1;
}
for(z1=1;z1<=m;z1++)
{
for(x=1;x<=m;x++)
for(y=1;y<=m;y++)
{
for(z2=max(1,z1-d);z2<z1;z2++)
res+=c[x][y][z1]*c[x][y][z2];
res+=c[x][y][z1]*(c[x][y][z1]-1)/2;
}
}
cout<<res<<'\n';
}
} Cube;
int main()
{
// freopen("pairs.inp","r",stdin);
// freopen("pairs.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int type; cin>>type;
if(type==1) Line.Work();
if(type==2) Grid.Work();
if(type==3) Cube.Work();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
18012 KB |
Output is correct |
| 2 |
Correct |
8 ms |
18012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
18012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
18012 KB |
Output is correct |
| 2 |
Correct |
17 ms |
18116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
18008 KB |
Output is correct |
| 2 |
Correct |
21 ms |
18012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
18064 KB |
Output is correct |
| 2 |
Correct |
22 ms |
18012 KB |
Output is correct |
| 3 |
Correct |
21 ms |
18012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
19036 KB |
Output is correct |
| 2 |
Correct |
14 ms |
19036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1049 ms |
192208 KB |
Output is correct |
| 2 |
Correct |
975 ms |
192024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1839 ms |
170140 KB |
Output is correct |
| 2 |
Correct |
2335 ms |
169892 KB |
Output is correct |
| 3 |
Correct |
1756 ms |
173300 KB |
Output is correct |
| 4 |
Correct |
1883 ms |
170732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2319 ms |
137720 KB |
Output is correct |
| 2 |
Correct |
2086 ms |
137360 KB |
Output is correct |
| 3 |
Correct |
809 ms |
136112 KB |
Output is correct |
| 4 |
Correct |
1000 ms |
147100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1839 ms |
278000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
53592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
734 ms |
228020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1810 ms |
279380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
