#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
namespace sub1 {
const int maxN = 1e5 + 20;
int pos[maxN];
int N, D, M;
void solve() {
cin >> N >> D >> M;
for (int i = 1; i <= N; i++) {
cin >> pos[i];
}
sort(pos + 1, pos + N + 1);
long long res = 0;
for (int i = 1; i <= N; i++) {
res += upper_bound(pos + 1, pos + N + 1, pos[i] + D) - lower_bound(pos + 1, pos + N + 1, pos[i] - D);
}
res = (res - N) / 2;
cout << res;
}
}
namespace sub2 {
void solve() {
assert(false);
}
}
namespace sub3 {
const int maxN = 1e5 + 20;
const int maxM = 80;
vector<pair<int, int>> pos[maxM];
int pref[maxM * 2][maxM * 2];
int N, D, M;
void build(int Z) {
for (int i = 0; i <= M * 2; i++) {
for (int j = 0; j <= M * 2; j++) {
pref[i][j] = 0;
}
}
for (auto p: pos[Z]) {
pref[p.first][p.second]++;
}
for (int i = 1; i <= M * 2; i++) {
for (int j = 1; j <= M * 2; j++) {
pref[i][j] += pref[i][j - 1];
}
}
for (int i = 1; i <= M * 2; i++) {
for (int j = 1; j <= M * 2; j++) {
pref[i][j] += pref[i - 1][j];
}
}
}
int get(int lx, int ly, int rx, int ry) {
lx = max(lx, 1);
ly = max(ly, 1);
rx = min(rx, M * 2);
ry = min(ry, M * 2);
return pref[rx][ry] - pref[rx][ly - 1] - pref[lx - 1][ry] + pref[lx - 1][ly - 1];
}
void solve() {
cin >> N >> D >> M;
for (int i = 1; i <= N; i++) {
int X, Y, Z;
cin >> X >> Y >> Z;
pos[Z].emplace_back(X - Y + M, X + Y);
}
long long res = 0;
for (int i = 1; i <= M; i++) {
build(i);
for (int j = max(i - D, 1); j <= min(i + D, M); j++) {
for (auto p: pos[j]) {
res += get(p.first - D + abs(i - j), p.second - D + abs(i - j), p.first + D - abs(i - j), p.second + D - abs(i - j));
}
}
}
res = (res - N) / 2;
cout << res;
}
}
void just_do_it() {
int B;
cin >> B;
if (B == 1) {
sub1::solve();
}
if (B == 2) {
sub2::solve();
}
if (B == 3) {
sub3::solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
716 KB |
Output is correct |
2 |
Correct |
23 ms |
712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
724 KB |
Output is correct |
2 |
Correct |
19 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
796 KB |
Output is correct |
2 |
Correct |
25 ms |
672 KB |
Output is correct |
3 |
Correct |
26 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
420 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
340 KB |
Output is correct |
2 |
Correct |
9 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
2124 KB |
Output is correct |
2 |
Correct |
23 ms |
2136 KB |
Output is correct |
3 |
Correct |
23 ms |
2068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
2252 KB |
Output is correct |
2 |
Correct |
56 ms |
2388 KB |
Output is correct |
3 |
Correct |
60 ms |
2344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
2516 KB |
Output is correct |
2 |
Correct |
69 ms |
2560 KB |
Output is correct |
3 |
Correct |
71 ms |
2568 KB |
Output is correct |