| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 686049 |
2023-01-25T05:27:00 Z |
finn__ |
Pairs (IOI07_pairs) |
C++17 |
|
316 ms |
524288 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 rotate45(Quaternion const &q)
{
return {q[0] - q[1] - q[2] - q[3],
q[0] + q[1] + q[2] - q[3],
q[0] - q[1] + q[2] + q[3],
q[0] + q[1] - q[2] + q[3]};
}
bool real_compare(Quaternion const &q1, Quaternion const &q2)
{
return q1[0] < q2[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;
}
break;
case 3:
for (Quaternion &q : animals)
{
cin >> q[0] >> q[1] >> q[2];
q[3] = 0;
}
break;
}
int64_t min_i = PTRDIFF_MAX, max_i = 0,
min_j = PTRDIFF_MAX, max_j = 0,
min_k = PTRDIFF_MAX, max_k = 0;
for (Quaternion &q : animals)
{
q = rotate45(q);
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(), 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 |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
536 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
246 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
7744 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
53 ms |
7760 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
34840 KB |
Output is correct |
| 2 |
Correct |
95 ms |
34840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
51 ms |
7644 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
8024 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
32468 KB |
Output is correct |
| 2 |
Correct |
14 ms |
32552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
4120 KB |
Output is correct |
| 2 |
Correct |
81 ms |
4044 KB |
Output is correct |
| 3 |
Correct |
66 ms |
4044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
25844 KB |
Output is correct |
| 2 |
Correct |
227 ms |
25836 KB |
Output is correct |
| 3 |
Correct |
108 ms |
25900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
316 ms |
46512 KB |
Output is correct |
| 2 |
Correct |
309 ms |
46508 KB |
Output is correct |
| 3 |
Correct |
138 ms |
46508 KB |
Output is correct |
