#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1'000'000'000;
struct Segment {
int x, y1, y2;
Segment(int x, int y1, int y2) : x(x), y1(y1), y2(y2) {}
};
ostream& operator << (ostream& os, const Segment &s) {
return os << "[x = " << s.x << "; y = " << s.y1 << "..." << s.y2 << "]";
}
bool adjacent(const Segment &a, const Segment &b) {
return abs(a.x - b.x) <= 1 && max(a.y1, b.y1) <= min(a.y2, b.y2);
}
vector<Segment> divide_into_segments(const vector<pair<int, int>> &blocks) {
vector<Segment> segments;
optional<Segment> currentSegment;
for (int i = 0; i < blocks.size(); ++i) {
if (!currentSegment) currentSegment = Segment(blocks[i].first, blocks[i].second, blocks[i].second);
else if (currentSegment->x != blocks[i].first || currentSegment->y2 + 1 < blocks[i].second) {
segments.push_back(*currentSegment);
currentSegment = Segment(blocks[i].first, blocks[i].second, blocks[i].second);
} else {
currentSegment->y2 = blocks[i].second;
}
}
if (currentSegment) segments.push_back(*currentSegment);
return segments;
}
ll pair_distance_sum(const vector<ll> &points) {
if (points.size() == 0) {
return 0;
}
ll ans = 0;
ll total = accumulate(points.begin(), points.end(), 0LL);
ll right_side = 0;
for (int i = 0; i < points.size(); ++i) {
right_side += points[i];
ans += right_side * (total - right_side) % MOD;
}
/*
cerr << "PDS " << ans;
for (ll v : points) cerr << " " << v;
cerr << endl;
*/
return ans % MOD;
}
vector<vector<ll>> segments_reachable;
ll sum_of_distances(int n, const vector<vector<int>> &tree, const vector<Segment> &segs, int v, int p) {
auto cseg = segs[v];
int length = cseg.y2 - cseg.y1 + 1;
segments_reachable[v].assign(length, 1);
auto comp = [&] (int y) {
return clamp(y, cseg.y1, cseg.y2) - cseg.y1;
};
ll ans = 0;
for (int child : tree[v]) {
if (child == p) continue;
ans += sum_of_distances(n, tree, segs, child, v);
int comp_min = comp(segs[child].y1), comp_max = comp(segs[child].y2);
vector<ll> csubsegment(comp_max - comp_min + 1);
ll segments_in_child = accumulate(segments_reachable[child].begin(),
segments_reachable[child].end(), 0LL);
for (int y = segs[child].y1; y <= segs[child].y2; ++y) {
ll segments_here = segments_reachable[child][y - segs[child].y1];
segments_reachable[v][comp(y)] += segments_here;
csubsegment[comp(y) - comp_min] += segments_here;
ll delta_y = abs(y - clamp(y, cseg.y1, cseg.y2)) + 1;
ans += delta_y * segments_here % MOD * (n - segments_in_child) % MOD;
}
ans -= pair_distance_sum(csubsegment);
}
ans += pair_distance_sum(segments_reachable[v]);
ans = (ans % MOD + MOD) % MOD;
// cerr << "SOD " << v << " (par " << p << " " << segs[v] << ") ans " << ans << endl;
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
segments_reachable.assign(N, vector<ll>());
vector<pair<int, int>> blocks(N);
for (int i = 0; i < N; ++i) blocks[i] = {X[i], Y[i]};
sort(blocks.begin(), blocks.end());
auto segments = divide_into_segments(blocks);
// for (auto &s : segments) cerr << s << endl;
int k = segments.size();
vector<vector<int>> tree(k);
for (int i = 0, j = 0, prev = 0; i < k; prev = i, i = j) {
while (j < k && segments[j].x == segments[i].x) ++j;
int cprev = prev;
for (int cseg_i = i; cseg_i < j; ++cseg_i) {
while (cprev < i && segments[cprev].y2 < segments[cseg_i].y1) ++cprev;
while (cprev < i && adjacent(segments[cseg_i], segments[cprev])) {
// cerr << "adjacent " << segments[cseg_i] << " " << segments[cprev] << endl;
tree[cseg_i].push_back(cprev);
tree[cprev].push_back(cseg_i);
if (segments[cprev].y2 <= segments[cseg_i].y1) {
++cprev;
} else {
break;
}
}
}
}
return sum_of_distances(N, tree, segments, 0, -1);
}
Compilation message
city.cpp: In function 'std::vector<Segment> divide_into_segments(const std::vector<std::pair<int, int> >&)':
city.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i = 0; i < blocks.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
city.cpp: In function 'll pair_distance_sum(const std::vector<long long int>&)':
city.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < points.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1592 KB |
Output is correct |
| 3 |
Correct |
11 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
13 ms |
3416 KB |
Output is correct |
| 5 |
Correct |
33 ms |
5980 KB |
Output is correct |
| 6 |
Correct |
24 ms |
6232 KB |
Output is correct |
| 7 |
Correct |
21 ms |
6480 KB |
Output is correct |
| 8 |
Correct |
21 ms |
5892 KB |
Output is correct |
| 9 |
Correct |
22 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
37 ms |
13768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
