| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 686130 |
2023-01-25T05:57:58 Z |
finn__ |
Pairs (IOI07_pairs) |
C++17 |
|
377 ms |
45672 KB |
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class FenwickTree3d
{
vector<T> t;
array<int64_t, 3> n;
public:
FenwickTree3d(array<int64_t, 3> const &_n)
{
n = _n;
t = vector<T>(n[0] * n[1] * n[2], 0);
}
private:
int64_t get_index(array<int64_t, 3> const &i) const
{
return (i[0] - 1) * n[1] * n[2] + (i[1] - 1) * n[2] + i[2] - 1;
}
T prefix_sum(array<int64_t, 3> i) const
{
T x = 0;
i[0]++, i[1]++, i[2]++;
while (i[0])
{
int64_t u = i[1];
while (u)
{
int64_t v = i[2];
while (v)
{
x += t[get_index({i[0], u, v})];
v -= v & -v;
}
u -= u & -u;
}
i[0] -= i[0] & -i[0];
}
return x;
}
public:
T range_sum(array<int64_t, 3> i, array<int64_t, 3> j) const
{
for (unsigned k = 0; k < 3; k++)
{
i[k] = min<T>(max<T>(i[k], 0), n[k] - 1);
j[k] = min<T>(max<T>(j[k], 0), n[k] - 1);
}
T x = 0;
for (unsigned k = 0; k < 8; k++)
{
array<int64_t, 3> const a = {k & 1 ? i[0] - 1 : j[0],
k & 2 ? i[1] - 1 : j[1],
k & 4 ? i[2] - 1 : j[2]};
if (a[0] >= 0 && a[1] >= 0 && a[2] >= 0)
x += prefix_sum(a) * ((__builtin_popcount(k) & 1) ? -1 : 1);
}
return x;
}
void increment(array<int64_t, 3> i, T x)
{
i[0]++, i[1]++, i[2]++;
while (i[0] <= n[0])
{
int64_t u = i[1];
while (u <= n[1])
{
int64_t v = i[2];
while (v <= n[2])
{
t[get_index({i[0], u, v})] += x;
v += v & -v;
}
u += u & -u;
}
i[0] += i[0] & -i[0];
}
}
};
typedef array<int64_t, 4> Quaternion;
Quaternion quaternion_multiply(Quaternion const &p, Quaternion const &q)
{
return {p[0] * q[0] - p[1] * q[1] - p[2] * q[2] - p[3] * q[3],
p[0] * q[1] + p[1] * q[0] + p[2] * q[3] - p[3] * q[2],
p[0] * q[2] - p[1] * q[3] + p[2] * q[0] + p[3] * q[1],
p[0] * q[3] + p[1] * q[2] - p[2] * q[1] + p[3] * q[0]};
}
bool quaternion_real_compare(Quaternion const &p, Quaternion const &q)
{
return p[0] < q[0];
}
int main()
{
size_t b, n, m;
int64_t d;
cin >> b >> n >> d >> m;
assert(b <= 3);
vector<Quaternion> animals(n);
switch (b)
{
case 1:
for (Quaternion &q : animals)
{
cin >> q[0];
q[1] = q[2] = q[3] = 0;
}
break;
case 2:
for (Quaternion &q : animals)
{
cin >> q[0] >> q[1];
q[2] = q[3] = 0;
q = quaternion_multiply(q, {1, 1, 0, 0});
}
break;
case 3:
for (Quaternion &q : animals)
{
cin >> q[0] >> q[1] >> q[2];
q[3] = 0;
q = quaternion_multiply(q, {1, 1, 1, 1});
}
break;
}
int64_t min_i = INT64_MAX, max_i = 0,
min_j = INT64_MAX, max_j = 0,
min_k = INT64_MAX, max_k = 0;
for (Quaternion &q : animals)
{
min_i = min(min_i, q[1]), max_i = max(max_i, q[1]);
min_j = min(min_j, q[2]), max_j = max(max_j, q[2]);
min_k = min(min_k, q[3]), max_k = max(max_k, q[3]);
}
for (Quaternion &q : animals)
{
q[1] -= min_i, q[2] -= min_j, q[3] -= min_k;
}
max_i -= min_i, max_j -= min_j, max_k -= min_k;
sort(animals.begin(), animals.end(), quaternion_real_compare);
int64_t ans = 0;
FenwickTree3d<int> tree({max_i + 1, max_j + 1, max_k + 1});
auto it = animals.begin(), jt = animals.begin();
while (it != animals.end())
{
while (jt != animals.end() && jt->at(0) <= it->at(0) + d)
{
tree.increment({jt->at(1), jt->at(2), jt->at(3)}, 1);
jt++;
}
tree.increment({it->at(1), it->at(2), it->at(3)}, -1);
ans += tree.range_sum({it->at(1) - d, it->at(2) - d, it->at(3) - d},
{it->at(1) + d, it->at(2) + d, it->at(3) + d});
it++;
}
cout << ans << '\n';
}
| # |
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 |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
3688 KB |
Output is correct |
| 2 |
Correct |
42 ms |
3796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
3420 KB |
Output is correct |
| 2 |
Correct |
53 ms |
4288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
58 ms |
4172 KB |
Output is correct |
| 3 |
Correct |
77 ms |
4304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
2 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
51 ms |
3420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
61 ms |
4176 KB |
Output is correct |
| 3 |
Correct |
62 ms |
4172 KB |
Output is correct |
| 4 |
Correct |
71 ms |
4176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
93 ms |
5080 KB |
Output is correct |
| 3 |
Correct |
81 ms |
5096 KB |
Output is correct |
| 4 |
Correct |
92 ms |
5072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
32484 KB |
Output is correct |
| 2 |
Correct |
14 ms |
32468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
3504 KB |
Output is correct |
| 2 |
Correct |
97 ms |
3424 KB |
Output is correct |
| 3 |
Correct |
65 ms |
3424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
202 ms |
25004 KB |
Output is correct |
| 2 |
Correct |
257 ms |
25000 KB |
Output is correct |
| 3 |
Correct |
106 ms |
25004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
377 ms |
45664 KB |
Output is correct |
| 2 |
Correct |
312 ms |
45668 KB |
Output is correct |
| 3 |
Correct |
154 ms |
45672 KB |
Output is correct |
