#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
ll b,n,d,m,x[N],y[N],z[N],ans;
ll pt=1,psum[150][150][150],par,dy;
vector<pair<int,int>> srt;
void sub1(){
for (int i=1;i<=n;i++){
cin>>x[i];
}
sort(x+1,x+1+n);
for (int i=1;i<=n;i++){
while (x[pt]<x[i]-d) pt++;
ans+=i-pt;
}
cout<<ans<<"\n";
}
const int D=37600;
struct bit{
const static int size=80050;
array<int,size> bit;
void modify(int id,int val){
for (;id<size;id+=(id&-id)) bit[id]+=val;
}
int query(int id){
int ret=0;
for (;id;id-=(id&-id)) ret+=bit[id];
return ret;
}
int query(int l,int r){
//cout<<l-D<<" "<<r-D<<endl;
return query(r)-query(l-1);
}
}cnt[2];
void sub2(){
for (int i=1;i<=n;i++){
cin>>x[i]>>y[i];
srt.emplace_back(x[i],y[i]);
}
sort(srt.begin(),srt.end(),[](pair<int,int> a, pair<int,int> b) {return a.first+a.second < b.first+b.second;});
auto curr=srt.begin();
for (auto i:srt){
while ((*curr).first+(*curr).second<i.first+i.second-d){
par=((*curr).first+(*curr).second)%2;
cnt[par].modify(((*curr).second-(*curr).first+par)/2+D,-1),curr++;
}
//cout<<i.first<<" "<<i.second<<endl;
par=(i.first+i.second)%2;
dy=(i.second-i.first+par)/2;
if (d%2){
ans+=cnt[!par].query(dy-d/2-1+D,dy+d/2+D);
ans+=cnt[par].query(dy-d/2+D,dy+d/2+D);
}else{
ans+=cnt[par].query(dy-d/2+D,dy+d/2+D);
ans+=cnt[!par].query(dy-d/2+2+D,dy+d/2+1+D);
}
cnt[par].modify((i.second-i.first+par)/2+D,1);
//cout<<ans<<"\n";
}
cout<<ans<<"\n";
}
void sub3(){
for (int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>z[i];
psum[x[i]][y[i]][z[i]]++;
}
for (int i=1;i<=75;i++) for (int j=1;j<=75;j++) for (int k=1;k<=75;k++) psum[i][j][k]+=psum[i][j][k-1];
for (int i=1;i<=n;i++){
for (int xx=max(1LL,x[i]-d);xx<=min(m,x[i]+d);xx++){
int dx=abs(x[i]-xx);
for (int yy=max(1LL,y[i]-(d-dx));yy<=min(m,y[i]+(d-dx));yy++){
int maxdz=d-dx-abs(y[i]-yy);
ans+=psum[xx][yy][min(m,z[i]+maxdz)]-psum[xx][yy][max(0LL,z[i]-maxdz-1)];
}
}
}
cout<<(ans-n)/2<<"\n";
}
int main(){
cin>>b>>n>>d>>m;
if (b==1) sub1();
else if (b==2) sub2();
else if (b==3) sub3();
else assert(0);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
980 KB |
Output is correct |
2 |
Correct |
24 ms |
1104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
1008 KB |
Output is correct |
2 |
Correct |
40 ms |
1008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
1080 KB |
Output is correct |
2 |
Correct |
41 ms |
1004 KB |
Output is correct |
3 |
Correct |
43 ms |
996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Runtime error |
2 ms |
1364 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
42 ms |
2836 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
54 ms |
2824 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
68 ms |
6496 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
7228 KB |
Output is correct |
2 |
Correct |
43 ms |
7124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
9448 KB |
Output is correct |
2 |
Correct |
75 ms |
9612 KB |
Output is correct |
3 |
Correct |
70 ms |
9516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
158 ms |
9512 KB |
Output is correct |
2 |
Correct |
1251 ms |
9548 KB |
Output is correct |
3 |
Correct |
1547 ms |
9516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
927 ms |
9548 KB |
Output is correct |
2 |
Correct |
2469 ms |
9548 KB |
Output is correct |
3 |
Correct |
3197 ms |
9516 KB |
Output is correct |