#include<bits/stdc++.h>
#define FileName "test"
#define ll long long
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
struct OneD {
int n, d, m; ll res = 0;
void Solve() {
cin >> n >> d >> m;
vector<int> v(n);
for(int& x: v) cin >> x;
sort(v.begin(), v.end());
for(int& x: v) res += upper_bound(v.begin(), v.end(), x + d) - lower_bound(v.begin(), v.end(), x - d);
cout << (res - n) / 2;
}
};
struct TwoD {
#define N 75000
#define M (N << 1)
int n, m, d, x, y, t[M];
vector<pii> v;
ll res;
void Update(int x, int val) {for(; x < M; x += (x & -x)) t[x] += val;}
int Get(int x) {int res = 0; for(; x > 0; x -= (x & -x)) res += t[x]; return res;}
void Solve() {
cin >> n >> d >> m; v.resize(n);
for(int i = 0; i < n; ++i) {
cin >> x >> y;
v[i].fi = x + y;
v[i].se = x - y + N;
}
sort(v.begin(), v.end());
int j = 0; res = 0;
for(int i = 0; i < n; ++i) {
while(v[i].fi - v[j].fi > d && j < i) Update(v[j].se, -1), ++j;
res += Get(min(v[i].se + d, M - 1)) - Get(v[i].se - d - 1);
Update(v[i].se, 1);
}
cout << res;
}
#undef N
#undef M
};
struct ThrD {
#define N 80
int cnt[N][N][N], D, xD;
int x, y, z, n, m, d;
vector<pair<pii, int>> v;
void Solve() {
cin >> n >> d >> m; v.resize(n);
for(int i = 0; i < n; ++i) {
cin >> x >> y >> z;
v[i] = mp(mp(x, y), z);
++cnt[x][y][z];
}
for(int i = 1; i <= 75; ++i) {
for(int j = 1; j <= 75; ++j) {
for(int k = 1; k <= 75; ++k) {
cnt[i][j][k] += cnt[i][j][k - 1];
}
}
}
ll res = 0;
for(int i = 0; i < n; ++i) {
for(int j = 1; j <= 75; ++j) {
if(abs(v[i].fi.fi - j) > d) continue;
D = d - abs(v[i].fi.fi - j);
for(int k = 1; k <= 75; ++k) {
xD = D - abs(v[i].fi.se - k);
res += cnt[j][k][min(v[i].se + xD, 75)] - cnt[j][k][max(v[i].se - xD - 1, 0)];
}
}
}
cout << res / 2;
}
#undef N
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if(fopen(FileName".inp", "r")) {
freopen(FileName".inp", "r", stdin);
freopen(FileName".out", "w", stdout);
}
int B; cin >> B;
if(B == 1) {
OneD one;
one.Solve();
} else if(B == 2) {
TwoD two;
two.Solve();
} else {
ThrD thr;
thr.Solve();
}
}
Compilation message
pairs.cpp: In function 'int main()':
pairs.cpp:92:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FileName".inp", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:93:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FileName".out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
1144 KB |
Output is correct |
2 |
Correct |
22 ms |
1144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
1660 KB |
Output is correct |
2 |
Correct |
29 ms |
1572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
1656 KB |
Output is correct |
2 |
Correct |
32 ms |
1656 KB |
Output is correct |
3 |
Correct |
29 ms |
1656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
888 KB |
Output is correct |
2 |
Correct |
3 ms |
1016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
1784 KB |
Output is correct |
2 |
Correct |
32 ms |
1776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
1972 KB |
Output is correct |
2 |
Correct |
39 ms |
1980 KB |
Output is correct |
3 |
Correct |
40 ms |
2040 KB |
Output is correct |
4 |
Correct |
38 ms |
1912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
2808 KB |
Output is correct |
2 |
Correct |
45 ms |
2808 KB |
Output is correct |
3 |
Correct |
43 ms |
2808 KB |
Output is correct |
4 |
Correct |
43 ms |
2936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
2332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
163 ms |
4088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1100 ms |
4216 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2676 ms |
4216 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |