#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
namespace Sub1{
ll solve(){
int n, d, m; cin >> n >> d >> m;
vector<ll> a(n);
for(int i = 0; i < n; ++i) cin >> a[i];
sort(ALL(a));
ll ans = 0;
for(ll i: a){
ans += upper_bound(ALL(a), i + d) - lower_bound(ALL(a), i - d) - 1;
}
ans /= 2;
return ans;
}
}
struct FenwickTree{
int n;
vector<ll> a;
FenwickTree(int _n){
n = _n;
a.resize(n+1);
}
void update(int i, ll v){
while(i <= n){
a[i] += v;
i += LASTBIT(i);
}
}
ll get(int i){
ll ans = 0;
while(i > 0){
ans += a[i];
i -= LASTBIT(i);
}
return ans;
}
ll get(int l, int r){return get(r) - get(l-1);}
};
namespace Sub2{
const int N = 150069;
vector<int> point[N];
vector<pair<int, int>> queries1[N], queries2[N];
ll solve(){
int n, d, m; cin >> n >> d >> m;
vector<pair<ll, ll>> a(n);
for(auto &i: a) {
cin >> i.first >> i.second;
i = make_pair(i.first + i.second - 1, i.first + m - i.second);
point[i.first].push_back(i.second);
pair<int, int> range = make_pair(max(1, i.second - d), min(m * 2 - 1, i.second + d));
queries1[max(1, i.first - d)].push_back(range);
queries2[min(m * 2 - 1, i.first + d)].push_back(range);
}
ll ans = 0;
FenwickTree bit(N);
for(int i = 1; i < N; ++i){
for(auto j: queries1[i])
ans -= bit.get(j.first, j.second);
for(int j: point[i])
bit.update(j, 1);
for(auto j: queries2[i])
ans += bit.get(j.first, j.second);
}
ans -= n;
ans /= 2;
return ans;
}
}
namespace Sub3{
const int N = 170;
int grid[N][N][N];
ll solve(){
int n, d, m; cin >> n >> d >> m;
vector<array<ll, 3>> a(n);
for(auto &i: a) {
for(auto &j: i) cin >> j;
grid[i[0]][i[1] + i[2] - 1][i[1] + m - i[2]]++;
}
for(int i = 1; i <= m; ++i) {
for(int j = 1; j < m * 2; ++j)
for(int k = 1; k < m * 2; ++k){
grid[i][j][k] += grid[i][j-1][k] + grid[i][j][k-1] - grid[i][j-1][k-1];
}
}
ll ans = 0;
for(auto i: a){
ll x = i[0], y = i[1] + i[2] - 1, z = i[1] + m - i[2];
for(int vcl = 1; vcl <= m; ++vcl) if (abs(vcl - x) <= d){
ll diff = abs(vcl - x);
ll x1 = max(1, y - diff), x2 = min(m * 2 - 1, y + diff);
ll y1 = max(1, z - diff), y2 = min(m * 2 - 1, z + diff);
ans += grid[vcl][x2][y2] - grid[vcl][x1-1][y2] - grid[vcl][x2][y1-1] + grid[vcl][x1-1][y1-1];
}
}
ans = (ans - n) / 2;
return ans;
}
}
ll solve(){
int b; cin >> b;
if (b == 1) return Sub1::solve();
if (b == 2) return Sub2::solve();
return Sub3::solve();
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
clock_t start = clock();
cout << solve() << "\n";
cerr << "Time elapsed: " << clock() - start << "ms!\n";
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... |