#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif
#define int long long
template<class T, int... Ns> struct BIT {
T val = 0;
void upd(T v) { val += v; }
T query() { return val; }
};
template<class T, int N, int... Ns> struct BIT<T, N, Ns...> {
BIT<T, Ns...> bit[N+1];
template<typename... Args> void upd(int pos, Args... args) {
for (; pos <= N; pos += pos&-pos) bit[pos].upd(args...);
}
template<typename... Args> T sum(int pos, Args... args) {
T res = 0; for (; pos > 0; pos -= pos&-pos) res += bit[pos].query(args...);
return res;
}
template<typename... Args> T query(int l, int r, Args... args) {
return sum(r, args...) - sum(l-1, args...);
}
};
int b, n, d, m, ans = 0;
BIT<int, 301, 301, 301> bit;
namespace sub1 {
void solve() {
vector<int> a(n);
for (auto& x : a) cin >> x;
sort(a.begin(), a.end());
debug(a);
int l = 0, r = 0;
for (int i = 0; i < n; i++){
while(r + 1 < n && a[r + 1] - a[i] <= d) r++;
while(l < n && a[i] - a[l] > d) l++;
ans += r - l;
}
}
}
namespace sub2 {
void solve(){
vector<array<int, 2>> a(n);
for (int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
a[i] = {x + y, x - y};
}
sort(a.begin(), a.end());
int l = 0, r = -1;
BIT<int, 150001> bit;
for (int i = 0; i < n; i++){
while(r + 1 < n && a[r + 1][0] - a[i][0] <= d){
bit.upd(a[++r][1] + m + 1, 1);
}
while(l < n && a[i][0] - a[l][0] > d){
bit.upd(a[l++][1] + m + 1, -1);
}
ans += bit.query(max(1ll, a[i][1] + m + 1 - d), min(2 * m + 1, a[i][1] + m + 1 + d)) - 1;
}
}
}
namespace sub3 {
void solve (){
vector<array<int, 4>> a(n);
for (int i = 0; i < n; i++){
int x, y, z;
cin >> x >> y >> z;
a[i] = {x + y + z, x + y - z, x - y + z, x - y - z};
}
sort(a.begin(), a.end());
int l = 0, r = -1;
for (int i = 0; i < n; i++){
while(r + 1 < n && a[r + 1][0] - a[i][0] <= d){
r++;
bit.upd(a[r][1] + 2 * m + 1, a[r][2] + 2 * m + 1, a[r][3] + 2 * m + 1, 1);
}
while(l < n && a[i][0] - a[l][0] > d){
bit.upd(a[l][1] + 2 * m + 1, a[l][2] + 2 * m + 1, a[l][3] + 2 * m + 1, -1);
l++;
}
ans += bit.query(max(1ll, a[i][1] + 2 * m + 1 - d), min(4 * m + 1, a[i][1] + 2 * m + 1 + d),
max(1ll, a[i][2] + 2 * m + 1 - d), min(4 * m + 1, a[i][2] + 2 * m + 1 + d),
max(1ll, a[i][3] + 2 * m + 1 - d), min(4 * m + 1, a[i][3] + 2 * m + 1 + d)
) - 1;
}
}
}
void solve(){
cin >> b >> n >> d >> m;
if (b == 1) sub1::solve();
else if (b == 2) sub2::solve();
else if (b == 3) sub3::solve();
cout << ans / 2;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
return 0;
}
# | 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... |