| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 681805 |
2023-01-14T12:52:40 Z |
finn__ |
Pairs (IOI07_pairs) |
C++17 |
|
146 ms |
43200 KB |
#include <bits/stdc++.h>
using namespace std;
struct point2d
{
int x, y;
bool operator<(point2d const &q) const
{
return x < q.x;
}
void rotate45()
{
x = x - y;
y = x + y;
}
};
int d;
bool event2d_compare(pair<point2d, bool> const &a, pair<point2d, bool> const &b)
{
int xa = a.second ? a.first.x : a.first.x + 2 * d,
xb = b.second ? b.first.x : b.first.x + 2 * d;
if (xa == xb)
return a.second && !b.second;
return xa < xb;
}
struct FenwickTree
{
vector<uint64_t> t;
FenwickTree(uint64_t n)
{
t = vector<uint64_t>(1 << (32 - __builtin_clz(n)), 0);
}
void increment(ptrdiff_t i)
{
i++;
while (i <= t.size())
{
t[i - 1]++;
i += i & -i;
}
}
void decrement(ptrdiff_t i)
{
i++;
while (i <= t.size())
{
t[i - 1]--;
i += i & -i;
}
}
uint64_t prefix_sum(ptrdiff_t i)
{
i++;
uint64_t x = 0;
while (i)
{
x += t[i - 1];
i -= i & -i;
}
return x;
}
uint64_t range_sum(ptrdiff_t i, ptrdiff_t j)
{
if (j >= t.size())
j = t.size() - 1;
if (!i)
return prefix_sum(j);
return prefix_sum(j) - prefix_sum(i - 1);
}
};
struct quaternion
{
int r, i, j, k;
quaternion(int x, int y, int z)
{
r = x + y + z;
i = x + y - z;
j = x - y + z;
k = x - y - z;
}
};
bool event3d_cmp(pair<quaternion, bool> const &a, pair<quaternion, bool> const &b)
{
int xa = a.second ? a.first.r : a.first.r + 2 * d,
xb = b.second ? b.first.r : b.first.r + 2 * d;
return xa == xb ? (a.second && !b.second) : xa < xb;
}
struct FenwickTree3d
{
vector<vector<vector<uint64_t>>> t;
FenwickTree3d(uint64_t n, uint64_t m, uint64_t l)
{
t = vector<vector<vector<uint64_t>>>(
1 << (32 - __builtin_clz(n)), vector<vector<uint64_t>>(
1 << (32 - __builtin_clz(m)), vector<uint64_t>(1 << (32 - __builtin_clz(l)), 0)));
}
void increment(ptrdiff_t i, ptrdiff_t j, ptrdiff_t k)
{
i++, j++, k++;
while (i <= t.size())
{
ptrdiff_t u = j;
while (u <= t[i - 1].size())
{
ptrdiff_t v = k;
while (v <= t[i - 1][u - 1].size())
{
t[i - 1][u - 1][v - 1]++;
v += v & -v;
}
u += u & -u;
}
i += i & -i;
}
}
void decrement(ptrdiff_t i, ptrdiff_t j, ptrdiff_t k)
{
i++, j++, k++;
while (i <= t.size())
{
ptrdiff_t u = j;
while (u <= t[i - 1].size())
{
ptrdiff_t v = k;
while (v <= t[i - 1][u - 1].size())
{
t[i - 1][u - 1][v - 1]--;
v += v & -v;
}
u += u & -u;
}
i += i & -i;
}
}
uint64_t prefix_sum(ptrdiff_t i, ptrdiff_t j, ptrdiff_t k)
{
i++, j++, k++;
uint64_t x = 0;
while (i)
{
ptrdiff_t u = j;
while (u)
{
ptrdiff_t v = k;
while (v)
{
x += t[i - 1][u - 1][v - 1];
v -= v & -v;
}
u -= u & -u;
}
i -= i & -i;
}
return x;
}
uint64_t range_sum(
ptrdiff_t i1, ptrdiff_t j1, ptrdiff_t k1,
ptrdiff_t i2, ptrdiff_t j2, ptrdiff_t k2)
{
i2 = min<ptrdiff_t>(i2, t.size() - 1);
j2 = min<ptrdiff_t>(j2, t[0].size() - 1);
k2 = min<ptrdiff_t>(k2, t[0][0].size() - 1);
uint64_t x = prefix_sum(i2, j2, k2);
if (i1)
x -= prefix_sum(i1 - 1, j2, k2);
if (j1)
x -= prefix_sum(i2, j1 - 1, k2);
if (k1)
x -= prefix_sum(i2, j2, k1 - 1);
if (i1 && j1)
x += prefix_sum(i1 - 1, j1 - 1, k2);
if (i1 && k1)
x += prefix_sum(i1 - 1, j2, k1 - 1);
if (j1 && k1)
x += prefix_sum(i2, j1 - 1, k1 - 1);
if (i1 && j1 && k1)
x -= prefix_sum(i1 - 1, j1 - 1, k1 - 1);
return x;
}
};
int main()
{
int b;
uint64_t n, m;
cin >> b >> n >> d >> m;
switch (b)
{
case 1:
{
vector<int> animals(n);
for (int &x : animals)
cin >> x;
sort(animals.begin(), animals.end());
auto it = animals.begin();
auto jt = upper_bound(animals.begin(), animals.end(), *it + d);
uint64_t total = jt - it - 1;
while (++it != animals.end())
{
while (jt != animals.end() && *it + d >= *jt)
jt++;
total += jt - it - 1;
}
cout << total << '\n';
break;
}
case 2:
{
vector<pair<point2d, bool>> animals;
int min_y = INT_MAX, max_y = INT_MIN;
for (uint64_t i = 0; i < n; i++)
{
point2d p;
cin >> p.x >> p.y;
p.rotate45();
animals.push_back({p, 1});
animals.push_back({p, 0});
min_y = min(min_y, p.y);
max_y = max(max_y, p.y);
}
for (auto &[p, b] : animals)
p.y -= min_y;
max_y -= min_y;
sort(animals.begin(), animals.end(), event2d_compare);
uint64_t total = 0;
FenwickTree tree(max_y + 1);
for (auto const &[p, b] : animals)
{
if (b)
tree.increment(p.y);
else
{
tree.decrement(p.y);
total += tree.range_sum(p.y, p.y + 2 * d);
}
}
cout << total << '\n';
break;
}
case 3:
{
vector<pair<quaternion, bool>> animals;
int min_i = INT_MAX, min_j = INT_MAX, min_k = INT_MAX;
for (uint64_t i = 0; i < n; i++)
{
int x, y, z;
cin >> x >> y >> z;
animals.emplace_back(quaternion(x, y, z), 1);
animals.emplace_back(quaternion(x, y, z), 0);
min_i = min(min_i, animals.back().first.i);
min_j = min(min_j, animals.back().first.j);
min_k = min(min_k, animals.back().first.k);
}
for (auto &[q, b] : animals)
{
q.i -= min_i;
q.j -= min_j;
q.k -= min_k;
}
FenwickTree3d tree(76, 76, 76);
sort(animals.begin(), animals.end(), event3d_cmp);
uint64_t total = 0;
for (auto const &[q, b] : animals)
{
if (b)
{
tree.increment(q.i, q.j, q.k);
}
else
{
tree.decrement(q.i, q.j, q.k);
total += tree.range_sum(q.i, q.j, q.k, q.i + 2 * d, q.j + 2 * d, q.k + 2 * d);
}
}
cout << total << '\n';
break;
}
}
}
Compilation message
pairs.cpp: In member function 'void FenwickTree::increment(ptrdiff_t)':
pairs.cpp:43:18: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | while (i <= t.size())
| ~~^~~~~~~~~~~
pairs.cpp: In member function 'void FenwickTree::decrement(ptrdiff_t)':
pairs.cpp:53:18: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (i <= t.size())
| ~~^~~~~~~~~~~
pairs.cpp: In member function 'uint64_t FenwickTree::range_sum(ptrdiff_t, ptrdiff_t)':
pairs.cpp:74:15: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if (j >= t.size())
| ~~^~~~~~~~~~~
pairs.cpp: In member function 'void FenwickTree3d::increment(ptrdiff_t, ptrdiff_t, ptrdiff_t)':
pairs.cpp:116:18: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<std::vector<std::vector<long unsigned int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | while (i <= t.size())
| ~~^~~~~~~~~~~
pairs.cpp:119:22: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<std::vector<long unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | while (u <= t[i - 1].size())
| ~~^~~~~~~~~~~~~~~~~~
pairs.cpp:122:26: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | while (v <= t[i - 1][u - 1].size())
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In member function 'void FenwickTree3d::decrement(ptrdiff_t, ptrdiff_t, ptrdiff_t)':
pairs.cpp:136:18: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<std::vector<std::vector<long unsigned int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | while (i <= t.size())
| ~~^~~~~~~~~~~
pairs.cpp:139:22: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<std::vector<long unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | while (u <= t[i - 1].size())
| ~~^~~~~~~~~~~~~~~~~~
pairs.cpp:142:26: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | while (v <= t[i - 1][u - 1].size())
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
696 KB |
Output is correct |
| 2 |
Correct |
23 ms |
676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
596 KB |
Output is correct |
| 2 |
Correct |
40 ms |
696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
680 KB |
Output is correct |
| 2 |
Correct |
40 ms |
676 KB |
Output is correct |
| 3 |
Correct |
39 ms |
680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
3460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
3496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
3656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
35284 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
21320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
146 ms |
43200 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
102 ms |
43180 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
