#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)
struct Fenwick{
vector<vector<vector<ll>>> tr; ll n, offs;
Fenwick(ll N){
n=N+20; offs=10;
tr.resize(n+1, vector(n+1, vector<ll>(n+1)));
}
void add(ll _i, ll _j, ll _k, ll x){
_i+=offs; _j+=offs; _k+=offs;
for (; _i<=n; _i+=(-_i&_i)){
for (ll j=_j; j<=n; j+=(-j&j)){
for (ll k=_k; k<=n; k+=(-k&k)){
tr[_i][j][k]+=x;
}
}
}
}
ll query(ll _i, ll _j, ll _k){
_i+=offs; _j+=offs; _k+=offs; ll sum=0;
for (ll i=_i; i; i-=(-i&i)){
for (ll j=_j; j; j-=(-j&j)){
for (ll k=_k; k; k-=(-k&k)){
sum+=tr[i][j][k];
}
}
}
return sum;
}
};
void solve(){
ll b, n, d, m; cin >> b >> n >> d >> m;
if (b==1){
vector<ll> cord(m+1), pref(m+1);
for (ll i=1; i<=n; i++){
ll x; cin >> x; cord[x]++;
}
for (ll i=1; i<=m; i++){
pref[i]+=pref[i-1]+cord[i];
}
ll res=0;
for (ll i=1; i<=m; i++){
if (cord[i]) res+=cord[i]*(pref[i-1]-pref[max(0ll, i-d-1)]+pref[min(m, i+d)]-pref[i]-1);
}
cout << res/2 << ln;
}else if (b==2){
vector<vector<ll>> to(2*m+1, vector<ll>(2*m+1));
for (ll i=0; i<n; i++){
ll x, y; cin >> x >> y;
to[x+y][x-y+m]++;
}
m=2*m;
vector<vector<ll>> pref(m+1, vector<ll>(m+1));
for (ll i=1; i<=m; i++){
for (ll j=1; j<=m; j++){
pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+to[i][j];
}
}
ll res=0;
for (ll i=1; i<=m; i++){
for (ll j=1; j<=m; j++){
if (to[i][j]) {
ll fi=max(0ll, i-d-1), fj = max(0ll, j-d-1);
ll ti = min(m, i+d), tj = min(m, j+d);
res+=(pref[ti][tj]-pref[ti][fj]-pref[fi][tj]+pref[fi][fj]-1)*to[i][j];
}
}
}
cout << res/2 << ln;
}else{
ll res=0;
vector<array<ll, 4>> a(n);
for (ll i=0; i<n; i++){
ll x, y, z; cin >> x >> y >> z;
a[i] = {x+y+z, x-y+z+m, x+y-z+m, x-y-z+2*m};
}
m=3*m;
sort(a.begin(), a.end());
ll l=0, r=-1; Fenwick tr(m);
for (ll i=0; i<n; i++){
while (l+1<=i and a[i][0]-a[l][0]>d) {
tr.add(a[l][1], a[l][2], a[l][3], -1); l++;
}
while (r+1<n and a[r+1][0]-a[i][0]<=d){
r++; tr.add(a[r][1], a[r][2], a[r][3], 1);
}
ll fx = max(a[i][1]-d-1, 0ll), fy = max(a[i][2]-d-1, 0ll), fz=max(a[i][3]-d-1, 0ll);
ll tx = min(a[i][1]+d, m), ty = min(a[i][2]+d, m), tz=min(a[i][3]+d, m);
// cout << tr.query(tx, ty, tz)-tr.query(tx, fy, tz)-tr.query(fx, ty, tz)-tr.query(tx, ty, fz)+tr.query(fx, fy, tz)+tr.query(fx, ty, fz)+tr.query(tx, fy, fz)-tr.query(fx, fy, fz)-1 << ln;
res += tr.query(tx, ty, tz)-tr.query(tx, fy, tz)-tr.query(fx, ty, tz)-tr.query(tx, ty, fz)+tr.query(fx, fy, tz)+tr.query(fx, ty, fz)+tr.query(tx, fy, fz)-tr.query(fx, fy, fz)-1;
}
cout << res/2 << ln;
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#ifdef LOCAL
auto start = chrono::high_resolution_clock::now();
#endif
ll t=1;
// cin >> t;
for (ll __c=1; __c<=t; __c++) solve();
#ifdef LOCAL
auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
#endif
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |