#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[N];
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];
// if(f[z][x][y][sum]>0)
// cout<<z<<" "<<x<<" "<<y<<" "<<sum<<'\n';
}
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)
res+=c[x][y][z1]*f[z2][x-1][y][max(1,x+y+z1-z2-d)];
// if(step==2 && z1==10 && x==20 && y==11) cerr<<c[x][y][z1]<<'\n';
// cerr<<f[z2][x-1][y][max(1,x+y+z1-z2-d)]<<'\n';
}
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 |
11 ms |
15808 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
17 ms |
16476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
16572 KB |
Output is correct |
| 2 |
Correct |
20 ms |
16476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
22 ms |
16476 KB |
Output is correct |
| 3 |
Correct |
21 ms |
16472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16984 KB |
Output is correct |
| 2 |
Correct |
11 ms |
16988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1819 ms |
275632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
51032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
762 ms |
209060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1878 ms |
275864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
